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; somebody@example.org
Arrival-Date: Mon,  5 Nov 2012 19:45:00 +0100 (CET)

Final-Recipient: rfc822; sbd@else.org
Original-Recipient: rfc822;sbd@else.org
Action: failed
Status: 5.7.1
Remote-MTA: dns; mx1.briefhansa.de
Diagnostic-Code: smtp; 554 5.7.1 Service unavailable; Client host
[1.2.3.45] blocked using b.barracudacentral.org;
http://www.barracudanetworks.com/reputation/?pr=1&ip=1.2.3.45

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!