Bei mir funktionierte die Suche gestern auch nicht, was extrem nervig war, weil ich die immer zum Starten von Programmen nutze (jedenfalls denen, die nicht fest an der Taskleiste angepinnt sind). Leider hatte ich die Heise-Meldung auch erst heute morgen gesehen.
Ich hatte gestern gegen Abend dann noch das aktuelle Funktionsupdate von Win10 eingespielt, danach funktionierte die Suche wieder. Das mag einfach ein zeitlicher Zufall gewesen sein oder es gibt tatsächlich ein Problem mit "alten" Windows 10-Versionen (vielleicht ist ja mal wieder ein Zertifikat abgelaufen?
).