What settings for Search do you have in Control Panel/ Folder Options/ Search? You could try restoring search defaults via that.
If you look at Indexing Options there is a choice via that to delete and rebuild the index.
If you are searching for hidden and system files then showing those files via Folder Options/ View may be necessary.
For machine wide searching you might have to look at extending your Indexing Options to cover all the folders otherwise searching may be slow.
This is from Windows 7 Help and Support.
"If you can't find a file, you can expand your search to include different locations. For example, if you're searching for a file in the Documents library, but you're not sure where the file is stored, you can search across all of your libraries or your entire computer. Here's how:
Click the Start button , and then click Documents.
In the search box at the top of the open window, start typing.
Scroll to the bottom of the list of search results. Under Search again in, do one of the following:
Click Libraries to search across every library.
Click Computer to search across your entire computer. (This way you can search for files that aren't indexed, such as system or program files, but remember that the search will be slower.)
Click Custom to search specific locations.
Click Internet to search online using your default web browser and your default search provider."
This might or might be useful.
Tips for finding files
Windows Search.