> That still requires the client to have downloaded all emails in the past in order to generate the Bloom filters.

That's generally not an issue. When people first create an email there is only 1 welcome email in the account. The client web/mobile/desktop downloads that one email and creates the search index.

If you get a new client/phone/desktop you can still reuse the encrypted index files. It's not like you have to download your last 5 years emails on each new device.