Couldn't the indexing issue be solved by only having the client/user do the indexing while e-mails are stored encrypted on the server? Ideally on an encrypted device which will keep/maintain the indexing.

Shifting the burden of indexing e-mail (and decrypting/encrypting the at rest) on the client willing to achieve this?

Edit:

The webmail/imap/pop provider would only have to receive an e-mail and use a client provide public key to encrypt the mail and let it rest.

The webmail client could (in browser) or through their app do the decryption/indexing locally. Could be done with an extension.