The only time I've experienced this is on a file that was downloaded but not installed. Installed applications pop up pretty quick. Not sure if Windows catalogs uninstalled files for their search.

Granted, on my Windows XP laptop at work, I use the run command for almost everything. Win then R then "cmd", "notepad", "firefox". It works pretty well for what I want it to do.