I think the key thing here is the context and size; the searchable content of even a lot of e-mails is quite dense and small. I'm not a search expert but I'd look at precalculated indexes on very short substrings (3-4 characters maybe?), have the client pull those it needs for a particular query and then process client-side from there. (Doesn't even need figuring out in advance what people will search for, though that'd certainly improve things.)

I did say you pay with engineering, didn't I? :)