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.