Scott Hanselman has blogged about it more than once, but I never listened. Now I've been converted. Go download Slickrun and quit leaning on the Start button. That's so... Windows 95. Magic Words is where it's at, baby!
One thing: Scott says he's got his Slickrun bound to Windows-R, so I followed his procedure to implement this. For some reason, it flakes out on me sometimes and displays the Windows Run dialog anyway. Since it's an inconsistent behavior, I figure it's probably just best to assign it to something else and get in the habit of invoking it from there (hopefully not the default Windows-Q, since that's pretty awkward).
Update: I figured out what was causing the flakiness. It seems that the difference is whether you use the left or right Windows key when performing Windows-R. At least, that's how it works on my Microsoft Natural Keyboard Elite at work. (Side note: The Elite model sucks, but it's the only one our desktop support team will purchase.)