Email NDR because of supposed invalid PTR (rDNS) record.

Hello, I am a sysadmin trying to find out why our emails are being rejected by AT&T.

The email is being sent from $user@$domain.com on a hosted Microsoft Exchange server mail.$domain.com to the recipient $email@bellsouth.net and we are getting a 550 5.7.1 NDR. 

Sanitized version of the NDR:

This message was created automatically by the SMTP relay on mail.$domain.com.
 
A message that you sent could not be delivered to all of its recipients.
The following address(es) failed:

 $email@bellsouth.net
 SMTP error from remote mail server after MAIL FROM:<$user@$domain.com>:
 host al-ip4-mx-vip2.prodigy.net [144.160.235.144]:
 550 5.7.1 Connections not accepted from servers without a valid sender domain.alph754 Fix reverse DNS for $static.ip

I have verified:

• The domain\ip is not on a public blacklist
• The PTR (rDNS) record is correct
• The original message was not a mass email, it was to one bellsouth email address

I have dealt with a similar issue for other ISPs. They required dual PTR records that consist of a standard ip → domain and ip → . The contents of the secondary record are unique to the ISP.

Comcast Example:

ip1= 12.345.678.9

ptr1= mail.$domain.com

ip2= 12.345.678.9

ptr2= 12-345-678-9-static.hfc.comcastbusiness.net

Sanitized nslookup:

PS C:\Users\LTJ_DNS> nslookup
Default Server: google-public-dns-a.google.com
Address: 8.8.8.8

> set type=ptr
> 12.345.678.9
Server: google-public-dns-a.google.com
Address: 8.8.8.8

Non-authoritative answer:
9.678.345.12.in-addr.arpa name = 12-345-678-9-static.hfc.comcastbusiness.net
9.678.345.12.in-addr.arpa name = mail.$domain.com
>

TLDR:

We have been able to email AT&T customers without isse for at least 5 years, but suddenly our messages are being rejected. We are not AT&T customers, but this seems to be a problem that is on AT&T's end. 

If we need additional ptr records, what are the requirements? What is the appropriate communication channel I need to seek?