Ich/wir haben das gleiche Problem hier in unserer Firma und bei Kunden. Unterschiedliche Exchange-Versionen (2013, 2016), betroffene Clients alle auf Windows 10 mit Outlook 2016 oder 2019. Suche mit OWA funktioniert.
Diverse Workarounds bzgl. Cache-Modus bringen entweder nichts oder sind nicht praktikabel, da vor allem Kunden oft jenseits des offline verfügbaren Zeitraums hinaus was suchen bzw. finden wollen.
Bei MEINEM Arbeits-PC (Windows 10 1909, Outlook 2019) hat nur der auf folgender Seite beschriebene Weg geholfen:
https://www.reddit.com/r/sysadmin/comments/gdvzuf/outlook_2016_exchange_search_not_working/ (in Englisch)
Hier in Kürze: Online-Downgrade auf das vorletzte Office-Build (12624.20466). Administrative CMD-Shell starten und darin
"%programfiles%\Common Files\Microsoft Shared\ClickToRun\officec2rclient.exe" /update user updatetoversion=16.0.12624.20466
absetzen.
Nach dem "Update" PC neu starten. Bei mir geht die Suche wieder. Habe sicherheitshalber in Office/Outlook die Updatefunktion deaktiviert.
Das bleibt so bis MS ein neues Update mit Fehlerbehebung anbietet. Und das hoffentlich bald, weil der Weg des Downgrade dem ein oder anderen Kunden
nicht vermittelbar ist.