It was never good when you compare to internet search.
On the internet I can search for "pictures of the eiffel tower". If I try the same on my own computer I expect to find photos from the time I took the family to paris... Yet I don't.
And yet Gnome and KDE have no troubles doing just that if you activate the corresponding plug-ins for the respective search engines (Tracker and Baloo). How you access them is a matter of taste, but both integrate into your runner dialog or launch menu, if you wish.
But that's not the point of the Start Menu. The purpose is to quickly start programs with a fixed name, not to do a natural language query. Yet it sucks with that simple task. If programs would add themselves to the PATH, then Win-R would be a worthy replacement. As they don't, it is not.