The other day I moved the email accounts of a customer system to a new dedicated server, then I changed the DNS entries for the mail domains. I later received the following email:
Reporting-MTA: dns;example.org X-Postfix-Queue-ID: D417F9C2389 X-Postfix-Sender: rfc822; email@example.com Arrival-Date: Mon, 5 Nov 2012 19:45:00 +0100 (CET) Final-Recipient: rfc822; firstname.lastname@example.org Original-Recipient: rfc822;email@example.com Action: failed Status: 5.7.1 Remote-MTA: dns; mx1.briefhansa.de Diagnostic-Code: smtp; 554 5.7.1 Service unavailable; Client host [126.96.36.199] blocked using b.barracudacentral.org; http://www.barracudanetworks.com/reputation/?pr=1&ip=188.8.131.52
It looked like the IP was added to the barracudas spam list. After some hours of digging through the mail server configuration I could not find any reason for that. Sadly many other partners of my customer mail systems were using those lists.
Following this excellent blog post and its comments, I found out that barracuda offers the option to pay 20 USD to (maybe) get off the list (this is exactly NOT what a spam-blacklist provider is supposed to do). I also tried to write them via the contact form they provide, but when I click the send button I get a php error page (fixed by now).
As hetzner.de was the server provider, I wrote them an email and asked for a new IP. It turned out that the IP the customer was provided with was used as a spam machine just before it was assigned to us. The IP address was then changed by hetzner within 2 hours.
So the only solution to this seems to be to get a new IP address. You should not pay money to barracuda!