I know what's wrong with windows vista search. It took me awhile to figure it out, sometimes it would work and sometimes it wouldn't. I hope this is the only problem, it works fine now. The normal or non-advanced search always worked fine but it only searches indexed locations, and even then if you open the search program and type even one letter in the search box in the upper left corner it will start searching and display many files that don't even have the letter you typed in the name. This is because it is searching the file name and contents also, if you only want file names searched, click on search tools->search options, click the search tab then under "what to search" choose "Always search file names only", also the default is to check the first two boxes under how to search. That should take care of a normal non-Advanced search, which I never use anyway and only started experimenting with it because I couldn't make the Advanced Search work at first.
When doing an Advanced Search, in the Name box enter a search parameter, for example ex*.exe (which will search for all .exe files that begin with "ex".) You'll probably want to change Location from "indexed locations" to either "everywhere" or "Computer" or a disk drive. Also, check the "Include non-indexed, hidden, and system files" box.
After clicking the Search button, "name:ex*.exe" and nothing else should appear in the search box(below the min/max/close buttons in the upper left corner of the window), if so the search should work fine. If there are characters or words before "name:ex*.exe" the search will result in "no matches found." I've found two ways in which this could happen.
1. You entered something in both the search box and the Name box and then clicked the Search button, the search box will now contain both of these entries. Example: enter xyz into search box and ex*.exe in the Name box, after clicking Search the search box will contain "xyz name:ex*.exe" and will result in no matches found.
2. The search box was auto filled when the Search program was started and you entered the search parameter in the Name box and then clicked the Search button. This is essentially equivalent to number 1. But you may not have realized that the search box was auto filled. This is what was happening to me.
To start the search program I was clicking on the start/windows button at the bottom left of the screen. Where it says "start search" I was typing in the word "search", then I would click on "Search Everywhere" to start the search program. Without my realizing it this would result in the word "search" I had typed in being auto filled into the search box in the search program. When I then entered my search parameter(example ex*.exe) in the Name box and clicked search,
"search name:ex*.exe" was appearing in the search box which always resulted in no matches found. It didn't dawn on me that the leading "search" part should not have been there. I only realized what was happening when I clicked on the Windows button and accidentally entered a few characters of garbage where it says Start Search. The "Search Everywhere" choice came up and I clicked it, I then realized the garbage I had entered had now been auto-filled into the search box when the search program started(duh, this is the way to do a quick search). After clicking on Advanced Search and entering my search parameter in the Name box and clicking the search button, the search box now contained the garbage I had entered followed by the search parameter (example "asds name:ex*.exe") which always results in no match found. All I had to do to fix this was click on the "x" to the right of the search box, directly below the "X" that closes the window in the upper left corner of the window. This resulted in "Search" appearing in the search box(nothing to do with the auto-fill "search" that had been appearing), when I clicked the search button again the "Search" disappeared and only "name:ex*.exe" appeared in the search box and everything worked fine.
I hope this is helpful to somebody.