My naive thought is that they could have an E2EE search index for each mailbox? I wouldn't even mind if the index storage counts against the quota.
Maybe over longer period it would be possible to integrate and maintain the index so, that you can guarantee the correctness without full mailbox.