Launchy does something like that. http://www.launchy.net/
Cross-platform and all.
Windows key + typing easily launches apps since, IIRC, Vista. As someone who is forced to use windows again, I was quite pleased that spotlight search to launch (available since Leopard) exists.
On OS X, I'm intensely addicted to Quicksilver. I know many others who use Alfred, or even the built-in Spotlight search feature, all of which are invoked from a readily accessible keyboard shortcut.
There must be a Windows equivalent? If not, here's a pro-tip for Microsoft: build a smart launcher in to the OS, and make the back-end pluggable so others can write their own alternatives and market them. Power users will shut up about the new Start screen, because they'll never bother with it. The rest of us will enjoy our shiny new dynamic tiles and can get on with our lives.