That stinks. I'm on Fastmail but its hard point has to do with being based in Australia and the recent government efforts of forcing entities to comply with police inquiries. Fastmail's side of the story: https://fastmail.blog/legal-policy/aabill-and-fastmail/
Fastmail rightly points out that the Australian law has no meaningful impact on them. They do not offer an end-to-end encrypted service, and hence, don't need to backdoor it.
The vast majority of mail services will hand your data to the government on court order. Though if your mail is hosted in a different country than you live in, it's arguably more frustrating for them to do so, since they must use international agreements to get it.
If state ordered surveillance is in your threat model, you need a very different type of mail service than almost everyone else.