If you need the server to be able to text search through your mail archive (and I do that a _lot_ on my phone), you need to "trust" the server with your clear text.
If you don't want to run and secure your own server - you need to choose what level of compromise you're prepared to accept.
My current project is a mail server on a RaspberryPi, hidden behind my home NAT gateway and firewall, that opens reverse ssh tunnels for ports 25 and 465 to inexpensive VPSes configured to not log anything - with IMAP (and webmail) access limited to my local network (and to my phone and iPad via vpn). It uses Vagrant and Ansible to provision and configure VPSes on the fly, and DNS hosting with APIs that Ansible can update MX records for as my receiving mail server moves around different VPS vendors in different jurisdictions.
How many megabytes of body text are you searching through? Is your phone actually incapable of doing the search in milliseconds?
The technical challenge is in designing a system in which the server does not have to be trusted, but that integrates well with existing protocols. I'm not aware of a proposal that offers the desired level of security while transparently integrating with SMTP, but perhaps Moxie has ideas.
One can get part way if the users generate their own key pair and only provide the server the public key, then either use a PGP-capable mail client or perhaps run a local (open source and audited) IMAP proxy to decrypt. You'd still have to trust the server not to store a clear copy of incoming mail, but once it is encrypted, only the client would be able to decrypt.