Can't resist!
I use a program I wrote, BCSearch
http://bc-programming.com/index.php?page=downloadsIt doesn't use any sort of indexing, though; so depending on the options used it can even take longer then Vista's file search, but for the most part it goes at least as fast as an unindexed search using the windows built-in tool. Interesting Features include the display of the alternate data streams of a file, something I don't believe I've seen in a file search program, as well as a number of other interesting enhancements.
It's certainly not the best file search program, but it doesn't compare badly with my competition, either.