Eventuell habe ich die "Lösung" gefunden:
Sofern die Option "Windows-Suche ermöglichen, Nachrichten zu durchsuchen" deaktiviert wird, scheint es (bis jetzt seit ein paar Tagen) besser zu laufen.
Edit: Sorry, hab gesehen, dass mein uraltes Problem schon auf Win8 bestand. Kurz nach Erscheinen bin ich auf Win10 x64 umgestiegen und das Problem bestand bei frischem TB weiterhin. Mein Win10 in der Firma hatte das Problem nie, allerdings hatte ich dort die Windows-Suchoption auch immer deaktiviert.
Vielleicht hilft es ja dem ein oder anderen