I am in the middle of moving from storing old emails in directories to storing them in a single directory called Reference and using Microsoft Outlook Categories to indicate the topic. After moving 3000 emails I found that nothing was returning in the search. I needed to force Outlook to re-index the emails.

I found this solution on line.

I had an indexing problem with Outlook 2010. I was moving the pst file around and the indexing got screwed up, so only emails that arrived after I finished the file move were indexed and appeared in search results. The ‘Delete and Rebuild Index’ did not index the older emails. What worked was removing Outlook from indexing, then rebooting, then adding Outlook back to indexing, then rebooting (the second reboot may be overkill, but it worked), then opening Outlook and attempting a search. That’s when it told me everything was being indexed. Here are instructions for removing/re-adding Outlook from indexing: Outlook 2010 Search Indexing (Hint: When you open Indexing Options and click Modify, uncheck Outlook and ‘ok’ out. Then after rebooting and going back into ‘Modify,’ check the box next to Outlook and ‘ok’ out.)

http://www.sevenforums.com/microsoft-office/121863-how-can-i-re-index-outlook-2010-a.html