Running the email through something like Amazon SES or Mandrill would probably be helpful. Both have generous free tiers.
So I don't know if that theory explains the issue either, though it could be a component.
[1] https://www.snellman.net/blog/archive/2014-12-05-how-buying-...
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.
Gmail's approach with a low-reputation IP is generally to throttle it aggressively; mail still gets through, just not very quickly if you're sending in bulk.
Domain reputation is not initially distrusted unless it's a brand-new domain (registered in the last 30 days or so), and generally doesn't come into play unless there's very unusually poor metrics (think sky-high spam complaints) associated with the domain. Content reputation is applied in a similar manner.
The headers I'm looking at should most likely give Gmail enough distinct identifiers to work with to isolate it from broader reputation issues at Hetzner, but the post only included partial headers, so I can't quite say that conclusively.
It's oh so much fun trying to get them removed.
But you are still sending all your outgoing email through an external 3rd party. Not ideal. Also, these days every email is a top-reply orgy of all correspondence ever sent, so your SMTP relay essentially gets a copy of your entire conversational inbox (via "QUOTE ALL THE THINGS" reply garbage) as well as your outbox.
smtp delivery is something of a black art, but at the very least those things need to be set correctly. Its also worth mentioning that if you have 'spammy' applications that opt people in to mailings then a lot of people just get pissed off and click the 'junk' button over and over instead of unsubscribing properly. So think twice before auto-subing customers or enabling 'mail me replies' by default on forums and such.
I also learned the hard way that once you're on Cisco Ironport's spam list, then you really can't get off. There's no one to talk to. Its supposed to be automated. In practice, that means months before your domain is unblocked. I find most Ironport admins just use that sole list even while Cisco recommends they use many and weigh the average. After a stupid config change that opened our smtp to relaying, we got off everyone's blacklist but IronPort. IronPort is pretty much the defacto standard in several types of enterprise. My fix? Get a different IP address for the mail server.
Mandrill is top notch, just like other professional email providers such as Mailgun and Sendgrid.
SES (as with Mandrill, Sendgrid, etc.) runs on a separate block of IPs and is very strict about spam/bounce reports. Very easy to get yourself throttled or cut off entirely.
You might have to spin up a bunch of servers to find one which doesn't have a blacklisted IP. Then you have to build the IP's "reputation" with the various providers before you can send a significant amount of email through it.
Just a few years ago, I personally experienced this sending email between two GMail accounts, and then I noticed that my (workplace!!) IP address ended up on a public blacklist within an hour. Fortunately I noticed fast enough to get it removed before any mail delivery was affected.
Good to know! I bet they have their own internal ranking system which is far more accurate than the public blacklists.
I've never had issues inboxing on gmail accounts using SPF/DKIM/DMARC + Sendgrid, even when sending 125,000+ emails (legit!) per day.
The primary limiting factor for most blacklists is not scale, but simply the fact that most of them have no more than a few data sources - most commonly spamtrap data. It's useful, but it's not a comprehensive enough data point to accurately evaluate mail.
Having dozens or hundreds of data points available - things like how many recipients open a message and spend time reading it, how quickly they seek out a message when initially opening their inbox, or a sending domain's pagerank - gives Google a considerable edge in assessing overall mail quality.
(Caveat: outbound filtering is often more difficult than inbound filtering - perhaps in part because there are fewer data points available when assessing outbound mail.)
I observed a former boss, who was very technically competent otherwise, using "mark as spam" instead of delete.
I guess if he could underestimate that button so can a million other people.
The fact that Linode's lowest tier has been $20/mo until recently ($10/mom nowadays) also helps. That makes Linode unnecessarily expensive for people who just want to burn IPs, since they can easily get an IP for $5/mo with DO or even less with low-end VPS providers.