I thought people might find this fix interesting because it annoyed the hell out of me when I first started using Vista. In the XP days, I was a huge Windows Desktop Search (WDS) fan, and like many WDS fans Vista search wasn't that exciting because of new features but rather, it gave visibility to mainstream windows users that desktop search would change the way they compute.
When I used WDS I typically indexed my whole C:\ and I carried that practice over to Vista's indexing service. That's when I started having issues. I wanted to to search all my content on the machine, but when I would search for any files in the Start Menu, I would never get any results returned on a search unless they were applications. For example, if I was to search for an excel file, it would not return in the Start Menu even though it was located in "Documents" -- it was very frustrating.
As it turns outs, the quick fix was to change the start menu settings so that the search bar is set to "search entire index" instead of the default "search this user's files." The problem arises due to the user changing the "indexed locations" to include all of the "C:" when the Start Menu is set to "search this user's files." This is a known bug and will be fixed in Vista SP1.
Since learning from this experience, I've changed my view on indexing all of the "C:\". Index only what you need to so that indexing performance as well as Start Menu search results are returned quickly. The reality is that if you properly use the USER namespace as opposed to ROOT for your documents and content, then you should never have a need to index all of the C:\
As a best practice, I keep all my temp files, downloads, logs and content in the Windows USER space. So remember, index what you want, but if you are insistent on indexing the whole disk before SP1, change the start menu settings to "search entire index" --VT