Gmail's email search is already the best in the space, by far. I'm sure there are improvements to be made, but zero external pressure to make them.

The new Inbox has "Top Hits", which is a more relevance-based search for email. It seems to work quite nicely, for me. I like that it gives you a couple highly-relevant emails, and the rest are still time-sorted for combing through all results.

When dealing with the public web, a search engine makes a single index of the web that millions of users can hit to perform searches. That amortizes the costs of generating and maintaining the index over a lot of people.

Your email corpus is private and specific to you. If Google (or any other company) generated a high-quality search index for it, they'd spend a lot of CPU hours on it and only amortize that across a single user: you.

I find Gmail search to work pretty well for me.

The question I have is why the Google Voice iPhone app does not have a search function AT ALL.

Last I checked, Gmail didn't do partial word searches. So “NewClient” won't match “GreatNewClient”. I think that's what rokhayakebe means.

It's one of the reasons I only use its backend. It baffles me that a company known for search can't do it.

I believe they're attacking the challenge from the opposite direction: Gmail search can be described as "okay" and Google works tirelessly to make the main Google.com search experience worse and worse -- eventually they will succeed in degrading it from its former excellence to a point where its quality matches Gmail's.