How about a mutually-trusted third party (somewhat like OpenID identity providers are supposed to work right now)? The mail service uploads your encrypted index to the search provider, you upload your key directly to them as well (possibly beforehand), and the search provider returns the results to the mail service. It's not quite client- or server-side, then, though; after all, you could specify the third party to be your own machine if you were paranoid, or their own server if you were lazy/unconcerned. It creates more of a flexible spectrum of privacy levels.