Nach 8 stündiger Suche habe ich den Fehler gefunden. Die Systemwiederherstellung hat übrigens nicht geholfen gehabt. Der traue ich eh nicht so, da ich damit oft Probleme hatte. (Fehlerhaft ausgeführt, nicht vorhanden etc.) Auf meinen MAC dagegen ist es sowas von einfach..., aber das ist ein anderes Thema! Windows halt..
Wie habe ich es nun gelöst? Dumme Idee gehabt, ich habe das Userinterface mal auf englisch umgeschaltet und nach der Englischen Fehlermeldung gesucht. Siehe da:
windows 7 start menu's search "see more results" broken - Super User
Lösung durch einen Microsoft Support Moderator:
Windows could not start the Windows Search service on Local Computer
Das Problem scheint bekannt, aber bis jetzt hat niemand eine Deutsche Lösung oder Hinweise diesbezüglich irgendwo gepostet. Daher:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows Search
Den Wert: "SetupCompletedSuccessfully" auf 0 setzen, oder wenn nicht vorhanden als neuen DWord Wert erstellen! (Simpler Indiz. rebuild oder Dienststart löst das Problem nämlich nicht!)
Neustart. Indiz, wird jetzt neu aufgebaut, indiz Verzeichnisse müssen komplett neu gesetzt werden, Problem behoben.
Grüße Greeny