Why is my email server in AT&T's blacklist?

I just got this bounce message:

<████████@att.net>: host scc-mailrelay.att.net[204.127.208.75] said:
    521-88.208.246.34 blocked by sbc:blacklist.mailrelay.att.net. 521 DNSRBL:
    Blocked for abuse. See http://att.net/blocks (in reply to MAIL FROM
    command)

So I'm trying to figure out why our server ended up on their blacklist. The web page link doesn't tell me why, as far as I can see. From a few multi-RBL tools I conclude that our IP is only on the collateral damage lists of uceprotect.net (you can be exempt from that with a paid subscription), and I dearly hope that AT&T doesn't use that.

From the mail server logs I see that an email to another @att.net address went through two days ago without being blocked.

Does anyone have any ideas how I can find out what went wrong?

Solution 1:

If you go to mxtoolbox.com and put in your IP, you can get a blacklist report. Your IP is on two of them:

• UCEPROTECTL2
• UCEPROTECTL3

Click the details next to the BL in question and it will tell you why you are on there and how to remove your self.

EDIT: I see that you already know that you are on the UCE Protect... Most mail admins use clearing house BLs that query all of the known ones, like SORBS, UCE, spamhaus, etc. You would need to talk with AT&T to determine which ones they are using. I noticed that they have a form you can fill out to find out why you were blocked...

EDIT2: Also, you should try adding your IP(s) to http://www.whitelisted.org. Supposedly, this will get around the UCE2 and UCE3.

rant
As a side note, I don't blame you for being upset at AT&T using UCE2 or UCE3. The people that run that blacklist have a bad attitude that is hurting everyone. They seem to think that you can switch ISPs on a whim when they won't shutdown a spammer. This mentality is just not practical in the current age of spam botnets of millions of computers scattered around the globe.
/rant

Solution 2:

If AT&T is indeed using uceprotect.net then go the route that Scott Lundberg hints at.

If not, then contact AT&T support and see what the specific reason is. They should have a process that you can go through to get your host removed from the block, or at least a process to apply to have it removed.