Gern geschehen!
In den letzten Tagen hatte ich das Problem bei mehreren Kunden und habe mir anfangs auch einen Wolf gesucht. Die Lösung stammt aus einem US-Forum, allerdings weiß ich nicht mehr, aus welchem genau.
Auch das Dezember-Update KB4471321 für Server 2016 killt auf RDS-Hosts reproduzierbar die Outlook-Suche.
Führe mal in einer administrativen Eingabeaufforderung DISM /online /Cleanup-Image /RestoreHealth und danach sfc /scannow aus. Vor und nach Eingabe der Befehle ist ein Neustart der Server empfehlenswert. Anschließend sollte die Suche wieder funktionieren (sofern das Update installiert sein sollte).