Outlook Fast Search doesn't return results

Symptom: You're in outlook, and the search results aren't as expected, or not returning anything.

Check here: http://office.microsoft.com/en-us/outlook-help/instant-search-is-not-finding-items-HA010198085.aspx

VERIFY THAT YOUR OUTLOOK DATA FILES CAN BE INDEXED
Outlook indexes the following data files:

Personal Folders files (.pst)
Offline Folder files (.ost)
This includes Microsoft Windows Live Mail, IMAP, and POP e-mail accounts. If you use a Microsoft Exchange account (much more common in business e-mail systems than in a home or personal account), you must be connected to the server running Exchange and use Cached Exchange Mode for Instant Search to index your messages. Cached Exchange Mode uses an Offline Folders file (.ost) to save your information on your computer. To verify which data files are being indexed, do the following:
On the Tools menu, point to Instant Search, and then click Search Options.
Alternatively, click the arrow in the Instant Search pane, and then click Search Options on the menu.

Under Indexing, verify that the data files that you want to include in your search are selected in the Index messages in these data files list.
VERIFY THAT INDEXING IS COMPLETE
To verify the indexing status, do the following:

On the Tools menu, point to Instant Search, and then click Indexing Status.
Alternatively, click the arrow in the Instant Search pane, and then click Indexing Status on the menu.

Verify that the dialog box reports 0 items remaining. If not, indexing is not complete and needs to finish before all of your Outlook items can be searched.
INDEXING STATUS REPORTS "0 ITEMS REMAINING," HOWEVER, SEARCH RESULTS ARE NOT CORRECT
If the Indexing Status reports 0 items remaining and Instant Search is still not returning the correct search results, exit Outlook and restart your computer. When you start Outlook again, verify that Outlook is indexing your items properly by doing the following:

On the Tools menu, point to Instant Search, and then click Indexing Status.
Alternatively, click the arrow in the Instant Search pane, and then click Indexing Status on the menu.

Verify that the number of items in the Indexing Status dialog box has increased. If the number has not increased, you must wait until indexing is complete for the results.

While you're looking at the checkboxes for what is supposed to be indexed, if you would like to start from scratch, clear the box[es] and OK through to exit the index search. Then go back and check them again, and OK out. This is what will take a few hours, but it will now index your email as if it never had done it before. Verify on occasion. The numbers should increase for a while, then decrease back to zero. Once completed, your index has been rebuilt.