But their encrypted in storage.

That's also the case for providers like Mailbox if you configure Inbox Encryption. But if you want, Mailbox never sees your private key, so even if they lie the blast radius is limited. And if they do something stupid you can easily move to another provider.