This problem appears on one of my computers once every few months. The Start menu search stops working without any reason. No matter what text I type in it, the results shown are completely empty!
What did not work
Killing the Explorer.exe process that displays the taskbar and Start menu and starting a new instance of it gets the search working again.
Here is how to do this:
Open Task Manager, go to the Processes tab, find the
Explorer.exe process and click End Process. There might more than one
Explorer.exe process, it is pretty harmless to kill them. You know you have killed the right one when the taskbar disappears.
In Task Manager, choose New Task and type in
explorer. This will bring back a fresh instance of Explorer.
Hopefully, the Start menu search should be working now.