If the domain is bitbin.de and the mail server is hosted on the same server, it's probably Hetzner being scorched-earth for deliverability, just like any other major hosting provider will be. Email from AWS, Rackspace, Heroku etc. get a drastically higher starting spam score because people fire up servers there to spam. Running the email through something like Amazon SES or Mandrill would probably be helpful. Both ha…
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…
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.