If you have a problem with Windows Search function, either not working properly or not working at all, there is one method that will most probably solve the issue.
Just follow these steps:
Go to Control Panel -> Programs -> Turn Windows features on or off
Look for Windows Search on the list and remove check mark in front of it.
Restart the system.
Go back to the same menu and add check mark in front of it this time.
Restart system again.
Voila, on this boot, Windows Search will most likely function properly again.
There are also many other features that can/might be repaired this way if you ever encounter issues for components listed there.
I have to verify Windows Vista as well, but I think it has the same control panel for internal components. Should also work for Win 8 as well…