No items match your search.
This message, "No items match your search", seems to imply that items were searched, and no matches were found.
But, on Vista, it also means "None of the items in the index match your search". There might be items that match your search, but maybe Vista hasn't indexed them yet, or maybe Vista is indexing them now.
I made a change to the default search options - because I caught it indexing a VMWare virtual hard disk image - and the change meant Vista needed to rebuild the index.
Next, I started doing some other stuff that needed documents from my hard disk. I'd search for them, and Vista would very quickly say "No items match your search" even for things that I know exist.
The workaround is to go to the folder you think the things might be in, right-click and pick Search, click Advanced, and turn on "Include non-indexed, hidden, and system files (might be slow)".
Of course, once again, Vista is lumping something I want - searching non-indexed files - in with stuff I don't want - searching system files. But at least I was able to find the documents I needed this way.
But seriously - if Vista is in the process of rebuilding an index, or for *any* reason might not be searching the entire range of documents that might contain my search text, it should tell me!
"No items match your search (but the search index is being rebuilt, so some files may not have been included in the search)".