Seems like when I search from the Start Menu, SearchIndexer.exe starts up. You might check Task Manager - Services - WSearch to see if that service is running. I suppose you get the same outcome if you use the Winkey + F?
Sorry if I am repeating something but it looks this thread was actually started somewhere else.
Edit: I can also get to show nothing if I uncheck the "Search programs and Control Panel" option on the start Menu Customize area. It seems the restore default suggestion should have changed this back.
I suppose the fallback position is to do an SFC /scannow in an administrative command prompt.
There is also a Search Troubleshooter you can run as admin if you haven't already.