Seems to me you can do this just as well on server side, and work more on ensuring Server<->Client interface security. Crypto tokens would be a start.
The way to tackle this would be to make index creation on the client incremental: any new messages are downloaded, decrypted, indexed, the index encrypted and uploaded back to the server. I'm not good enough with either search/indexing or crypto to know how you'd use such an incremental encrypted index to perform an actual search without having to decrypt (and therefore download) the entire index first. In fairness, I haven't researched this yet.
Securing the client-server comms is a solved problem, I'm not aware of any problems with SSL/TLS as long as the server also authenticates itself (which current browsers don't permit, but is easy to do with SSL directly).
Caveat: I'm neither cperciva nor tptacek (let alone Bruce Schneier) so there's a high probability I made some factual mistakes in this post.
There has also been a lot of theoretical work in topics like predicate- and functional-encryption which could eventually be used for richer queries.