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…
This seems to also be the case with DO, I setup a mail server on an instance there and can't escape people's spam boxes.
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.