Search indexes are very large -- you don't want to double or triple the amount of storage your email client uses. Also, being able to search only mail that you've downloaded and decrypted is a terrible user experience. I'd estimate over 60% of the mail to my personal inbox is from some automated system, rather than directly from a human, and I typically don't look at them unless a search hits them.
It takes 5 seconds to think of solutions with terrible security and usability characteristics. Thinking of a system that will be a measurable improvement in security and will actually be used by people is much more difficult.
The fact that you can't identify any ways in which they could, or refuse to acknowledge them, or think they're too difficult for a multi-billion dollar company makes no difference to the point under discussion.
Client side tool which builds a local index as messages are decrypted to be read for the first time. The index is it's self encrypted and incrementally synced between clients.
That took me less than 5 seconds to think up. Google can spend time and money thinking up better solutions if they want to actually do something.