Aside from Unity, KDE and Cinnamon, which of the many desktop environments support incremental search among the start menu items, including not just applications, but recent documents?
That is, which DEs integrate semantic search systems like Synapse (no longer maintained), Kupfer or GNOME Do?
LXDE and XFCE do not, for example, though in XFCE you could press Alt+F2 and click the down arrow to search among installed applications (recent documents aren't added to this menu).
(Ideally, this menu would be activated when the Win/Super key was released, which seems almost impossible to achieve, though Cinnamon does it)
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.
Unity Dash has nice search functions, and easy extendable via scopes and lenses.