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.