Earlier quoted context omitted.
I run a server on Hetzner that sends maybe 100k messages a week, and appears to have no problems with delivery. It doesn't even have SPF or DKIM set up. And I'm pretty sure that if messages were not getting delivered, users would complain. At least that's exactly what happened the one time there was a configuration screwup [1] that made some email providers reject mail from that server. So I don't know if that theory…
> I run a server on Hetzner that sends maybe 100k messages a week, and appears to have no problems with delivery. That volume (assuming non-spammy content, of course) would over time build up a positive reputation for your IPs, outbound addresses, and content. A new or low-volume IP on Hetzner is going to have a harder time overcoming the initial suspicion Gmail saddles it with.
It's oh so much fun trying to get them removed.