I use Mail on OS X and it is good enough for my purpose. Could certainly be a bit more sophisticated, but most of the time, it works. I like to have a real email client for my mails and not use a web app.

There might be dedicated search engines for emails though, if search is very important.

See, if you use search a lot and Google has the superior product for your use case, that's totally fine. But I guess most people use Gmail out of habit and not because it is truly superior to other email clients.

Searching is a solved problem if you use OfflineIMAP to mirror your mail store locally, then run mu or notmuch on top of it. Honestly, it's faster for me to search my local mail store than using some web interface. Plus, i can do it in the train when i have no internet connection. I happily pay a few euros a month for an email server which provides me with IMAP.