Outlook Suche in Archiv funktioniert nicht

Ich habe folgende Umgebung:

Windows Domäne mit Win10 Clients und Server 2012 DC, Exchange 2010, Outlook 2013.

Bei manchen Benutzern funktioniert die Outlook Suche in Archiven nicht: "Das gesuchte Element wurde nicht gefunden". Egal was man als Suchbegriff eingibt. Die Suche steht auf "aktueller Ordner" und ich suche nach dem Betreff der ersten/obersten Mail.
Die Archive liegen auf den Home Laufwerken und sind in Outlook als Datendatei eingebunden. Von jetzt auf gleich funktioniert die Suche auf einmal nicht mehr. Datendatei von einem betroffenen Benutzer auf dem betroffenen Rechner ist ca. 3 GB groß.

Das kuriose: Meldet sich der Benutzer auf einem anderen PC an, funktioniert die Suche einwandfrei. ScanPST findet keine Fehler in der PST Datei. Office online und auch komplette Reparatur hat keine Abhilfe gebracht. Über die Systemsteuerung - Indizierungsoptionen - Erweiterte Optionen - Index löschen und neu erstellen - hat nicht geholfen.

Outlook aus der Liste der "einbezogenen Orte" rauszunehmen, neu zu starten, wieder reinzunehmen hat auch nicht geholfen.

Auf dem betroffenen PC funktioniert die Suche für andere Benutzer aber schon, auch in seinen Archiven.

Woran kann das liegen und wie kann man das beheben?
Ich probiere gerade schon aus das Benutzerprofil vom Rechner lokal zu löschen über die Systemsteuerung (ja, ich weiß, ist nicht 100% sauber danach) und ihn sich neu das Profil vom Server laden zu lassen. Aber da muss es ja auch irgendwo etwas geben, was man gezielt löschen kann, um die Suche wieder in Gang zu bringen?

Die Suche auf dem Exchange im Exchange Postfach selbst funktioniert im selben Moment.
Mit dem Benutzer nur ein neues Mailkontoprofil anzulegen hat nicht ausgereicht, um die Suche wieder ans laufen zu bringen.

Danke für Hilfe.