For me at least, this would be completely unacceptable as a search replacement, as I frequently search old message bodies. ... 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.
Just install Mozilla Thunderbird and use IMAP. Client side search, all your devices sync via IMAP, no ads, and free software.
FWIW, I've evaluated email clients from time to time, but haven't found anything I like enough to replace Gmail. I haven't tried Thunderbird for years because I don't want to use a client without conversation view, and Thunderbird doesn't seem to offer it as a core feature; I could try one of the extensions for it, but I'm suspicious it won't work well. Also, I'm not sure I want to start using a product that's been on life support for two years. However, I admit these are relatively small turnoffs, so perhaps I should give Thunderbird a spin some time...
Anyway, it's off topic.
> I don't want to use a client without conversation view, and Thunderbird doesn't seem to offer it as a core feature
Actually it does, sort of: Right click on [email protected], choose Search Messages, then Save as Search Folder, then "Match all Messages" and, in "Select the folders to search", Inbox and Sent.
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.