I moved from DigitalOcean to Hetzner, and Gmail started marking all my emails as spam, most likely due to bad IP reputation. I moved to Zoho Mail [0] (at €10.80/user/month), which doesn’t have problems like these, and requires less work to manage.
That's weird. I'm running a mail server at Hetzner for years now and never got a mail rejected. Maybe you just got bad luck with the IP, which could be flagged at Spamhaus, etc.