Do you really have trouble with Mail.app search? Because I find it STARKLY better than Outlook.

Granted, creating any kind of complex multi-clause query is a pain, but for simple searches it never lets me down whereas Outlook often just fails to find things I know are present.