Let's try doing things step by step - please perform the following action, then post the results: 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.
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.