I've used Launchy on Windows. Launchy is okay, but it requires a lot of babysitting. Searchable folders have to be tweaked to get decent results.
I've recently started using Fedora 13. Naturally I wanted a launcher. Wikipedia has a nice comparison of launchers. I installed Gnome Do from yum :
sudo yum install gnome-do
Its fast and returns meaningful results quickly. Its also written in Mono which I find marginally interesting.