Das mit der Suche hatte ich auch. Kannst über die Systemsteuerng (die alte; Rechtsklick dafür auf das Windows Logo -> Systemsteuerung) -> Indizierungsoptionen prüfen, ob unter Einbezogene Orte alles steht was dir wichtig ist. Wenn Programme sich ins Startmenü eintragen reicht das. Daran solltest du erst was ändern wenn Schritt 2 unten nicht funktioniert.
Wenn du auf Erweitert gehst, gibt es da dann noch den Button Neu erstellen. Das dauert dann, je nach Alter der Installation (also vor dem Upgrade etc) etwas, aber danach sollte es wieder gehen.
Vielleicht danach mal rebooten. Im TaskManager schauen ob die Suchdienste/Indizierungsdienste laufen.
->