Hallo,
ich hatte das Problem mit Win 10 pro 64bit und Outlook 2016 gerade auch, keine E-Mails mehr zu finden.
Was sofort half, war Outlook im abgesicherten Modus starten (Strg Taste halten und Outlook mit Doppelklick starten).
Das brachte im "normalen" Modus aber keine Verbesserung.
Dann bin ich über die Indizierungsoptionen (Systemsteuerung) -->Erweitert -->Index löschen und neu erstellen rein und habe den Index gelöscht und neu angelegt, sowie über Taskmanager -->Dienste -->Windows Search neu starten.
Ergebnis bei mir: Suche läuft wieder einwandfrei. :-)
LG Frank