If your search index is corrupt or you suspect it's corrupt, you can easily rebuild the index.
There are several ways to access the Indexing options dialog:
From Windows, go to the Control panel and look for "Indexing options", or start typing indexing options in the Start Search field if using Windows 7 and Vista and press Enter when it comes up.How to hide paragraph formatting marks
Will Outlook warn me if mail is stuck in the outbox? » »