Considerable value of the search functionality can be retained by restricting it to metadata like originator which needs to be accessible for delivery to work anyway.
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.
Anyway, it's off topic.
Actually it does, sort of: Right click on you@example.com, choose Search Messages, then Save as Search Folder, then "Match all Messages" and, in "Select the folders to search", Inbox and Sent.