I went with https://mailfence.com a small Belgian provider called. I needed to contact their support only once, and they were prompt and helpful. The only shortcoming compared to Gmail is their web interface is a bit minimalistic, but fully functional and incredibly fast, also on mobile.

Other mentioned Fastmail, which is also fine as a provider, but I somehow trust EU / Belgian regulations more than Australian.

EDIT: Replied to the wrong post, I wanted to actually reply to the parent post.