At my last job I used Outlook and was very frustrated by the speed of searching my mail. Outlook seemed to take ages; Gmail on the other hand excels at searching.

Disclaimer: I don't have as much experience with Outlook as I do with Gmail. And it could very likely have been the backend at my last place.