This is the only reason why I did not go with fastmail. I am still looking for an alternative to gmail though...

Making your decision based on that doesn't make sense, because it doesn't affect FastMail at all. They're not an end-to-end encrypted service. They can already access all of your data without a backdoor (and need to be able to, to provide features like search).

More info in this blog post, specifically under "The AABill doesn’t change your privacy or data security with FastMail": https://fastmail.blog/2018/12/21/advocating-for-privacy-aabi...

I've been using posteo.de. I haven't heard anything negative about them, they're not terribly expensive, they support IMAP (unlike protonmail), and support is excellent (had issues syncing contacts to a BBOS10 device they solved immediately)