In my travels amongst ISVs, I find very technical folks who find search in Vista a little, well…, rudimentary for their needs. I.e. those who still prefer dir /s *foo*.xml in some directory tree where we know there *should* be an xml file that contains foo in the name. I love the new instant search box in Vista's file explorer, but in order to truly love it, you need more than just the basics.
One of the initial misconceptions I find amongst users is that when you type a search term in that box, Vista does a keyword search of the file contents and does not explicitly search only the filename. If you want to search just on the filename (as we're used to doing), type filename:foo where foo is some portion of the filename. You don't need wildcards (*) in order to find files this way. Another common need is to search files of a certain extension, i.e. ext:.xml for all xml files relative to the directory you are browsing.
Search becomes even more powerful when you start combining search constructs such as filename:foo and ext:.xml for all xml files that have foo in the name. Another great use of these powerful constructs is to save your search, which creates a virtual Search Folder. You can find all the advanced search terms available here.
Be happy "using the tools" in Vista J, sometimes we need to embrace a little change to fully appreciate the value!