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.)