What desktop environments feature a searchable "Start" menu/launcher?
Sounds like Gnome Shell to me. Have a try: http://www.gnome.org/gnome-3/
Enlightenment 17 supports this feature through a module called "Run everything". It is not necessarily as intuitive as the others, but with a little "getting used to" it can be pretty useful and quick.