If you are encountering problems with the searching engine built into Windows Vista, your best bet is to tell the indexing service to completely rebuild the index. It will take a while to rebuild, but it's usually worth it.

It's important to note that the search indexing in Windows Vista also handles searching in Microsoft Outlook 2007, so if you are encountering errors there you have another troubleshooting step other than disabling instant search.

Type in indexing into the start menu search box to launch Indexing Options:

Once the dialog opens, you'll want to choose the "Advanced" button, which will give you a UAC prompt.

Now you can simply click the Rebuild button, and the search index will be wiped clean and regenerated.

This process does take a long time if you have many files being indexed, so you might want to consider trimming down the indexed locations.