That still requires the client to have downloaded all emails in the past in order to generate the Bloom filters. Those filters can't be provided by the server.

Which is maybe fine if you're starting an e-mail account from scratch, but it is going to take a long time to set up email search on a new phone.

Also e-mails are a pretty bad use case for Bloom filters because you need to construct an entire filter per-email for search. Since many emails are short (a sentence or two) you'll find each Bloom filter may actually be larger than the e-mail itself.

I don't know if there are other types of probabilistic filters more suited to e-mail search however.