I'm not sure how I did anything on XP before I started using app launchers. My first was Colibri, but then I found my true love, Launchy. It's so liberating not to have to click the start menu(press ctrl+esc or win key), then find programs(press p) and then search through a gigantic list of stuff for what you want. With Launchy, you just hit your short cut key and start typing in what you want.
Vista's start menu comes with a similar search box that let's you type in what you want. I think that they threw this in because actually going to Programs and looking for what you want is a hideous experience in Vista. I keep all my applications that don't require an installation in a separate folder named "Programs". Vista doesn't search this folder by default, so I had to modify the settings for the start menu... no, no... that's not it. Maybe it's the user preferences... no, that's not it either. Oh there it is, in the indexing service.
In the Vista search box type "index" and it should find "Indexing Options". Inside Indexing Options click the Modify button to specify which folders to index. I actually turned off a few that I didn't care about. Things like other user's folders, and Outlook. You can actually disable the service all together if you want to get a slight performance boost, but I like the search bar too much to kill it.
For those of you who are keyboard bound like me, might I also suggest using SlimKeys in conjunction with the Vista search. SlimKeys comes with an app launcher, but I disabled it. I am using it's hotkey manager, window positioner/sizer, volume controller, screen grabber and it's format removing paster. I highly recommend checking it out just for the window positioner/sizer. It's great to be able to move a window to any corner, or center it or maximize it and even move it to my other monitor with a single keystroke.