Sadly, we tried with AT&T (and their subsidiaries that use the same rules -- I think it's AT&T, BellSouth, and SBC Global) for a very long time and were unable to convince their systems that we were legit mail senders. (If I remember correctly, we managed to get unblocked after a few months, for a grand total of about two weeks before they blocked us again.) They're very aggressive in blocking mail senders, and very reluctant to unblock again.

The alternate system we're in the middle of implementing may work better for you, but I can't guarantee it. Sorry!

(Email is the absolute worst technical problem to solve. The worst.)