How to rebuild the search index

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.

You can also access it from Outlook 2010's File, Options, Search dialog.
Outlook's Instant Search options dialog

After opening the Indexing options dialog, click the Advanced button, then the Rebuild button.
Rebuild search index in Outlook