Problem ist seit längerem bekannt. Ausführliche Beschreibung unter
https://techcommunity.microsoft.com/t5/outlook-global-customer-service/how-outlook-2016-utilizes-exchange-server-2016-fast-search/ba-p/381195
unter all den Möglichkeiten hat für mich die vielleicht einfachste funktioniert: FAST Search abschalten
https://www.managed-office.at/wissensdatenbank/item/outlook-suche-funktioniert-nicht
d.h. ein Registy-Patch ist nötig.
Happy searching!