Recently our domain has been getting rejected from any one of the dozen or so domains out there that are part of AT&T (bellsouth, snet, sbc, etc, etc). Up until last Friday eveything worked just fine, and since then, chaos. While my company maintains our own Exchange server, we have a number of outside users around the country (not to mention customers) that rely on AT&T DSL, so our office is in the lurch. According to at least one AT&T customer rep, there were some changes made to AT&T mail servers that tightened security, but I don't know how reliable that really is.
Anyway, we own several domain names which point back to our Exchange server and all but one of the A and MX records for these domains are kept at Godaddy.com. The lone standout is instead kept with our ISP. All of the MX records at Godaddy point back to the domain kept at our ISP as well.
So far, it seems that I can send email to any of the AT&T sites if I go into Active Directory, select one of our users, and change their primary email address to use the domain that is kept with our ISP. If a user has primary email from a domain hosted at Godaddy, I get rejections. Nothing has changed at our end, nor at Godaddy. I've double-checked to make sure there is no open-relay issues and to the best of my knowledge we aren't one.
I have since sent a request to at&t to get off of their blacklist, and for some of the AT&T domain it seems to have worked. But other AT&T domains are still rejecting our messages.
I don't know if I'll get a perfect answer for this, but if anyone has run into trouble with AT&T domains before, perhaps I can get a bit more enlightenment for it. :)