When I worked in marketing, I had Outlook search flat out refuse to find emails in my Inbox, through both header searches and body searches.

Totally undeterministic behaviour, because it would turn around and work on other searches.