For me at least, this would be completely unacceptable as a search replacement, as I frequently search old message bodies. Not to mention that there's no reason originator can't be encrypted at rest, at least in theory..

However, based on the experience of desktop search, I think pure client side search would probably have reasonable initialization time and space overhead, and would certainly make searches faster, at least compared to my current Gmail experience.