For two years, I have battled with this issue of Bellsouth.net (and AT&T in general) blocking email from any domain hosted on my web server. I set up all kinds of security precautions, set up SPF records, and ran all sorts of tests in order to subdue the fears that somehow my server was being used as an open relay for spam.
I was so sure that it was all correct, and was so frustrated that the problem wouldn’t go away. It only appeared to happen with Bellsouth addresses.
I used the AT&T Unblock request twice, which helped for a short time, but I would soon find email being blocked again and many of my hosted clients complaining.
But today, scouring through the CPanel user forums, I discovered the cause and solution!
I had a hosted client who wanted me to forward all of her email to her Bellsouth account a couple of years ago. I did this, and then she soon complained that she wasn’t receiving any email. I never stopped to consider the fact that the forward itself was the cause of the problem, and that Bellsouth thought that there was spam being relayed from my server!
So, I have removed that forwarded email account (got her to set up a GMail account), have re-filed a request with Bellsouth to unblock my server, and all should be good again.
I hope this helps someone out there!