However, Debi noticed that AT&T's network wasn't accepting email from our mail servers. It didn't matter what the FROM domain was on the messages, the message's were not delivered to them. I first tested by sending email to my Hotmail, Gmail and Yahoomail accounts, and the messages showed up in the inbox, which I thought was pretty good — I figured that at least one of those provided would "bin" my messages.
I called Verizon's tech support (who are very knowledgeable and helpful) and they said that they didn't have a smart host that I could use. However, if I wanted to try, I could use the authenticated SMTP server they provide for users' email applications, and then configure the Exchange Server to send credentials to that machine to use it for outbound relay. The problem, they told me is if you sent too many messages too quickly, the account might be tagged as a spammer and shut down the server. For that reason, they didn't recommend that I use my personal SMTP account as a smart host.
So, we went with the rDNS record. It was very easy to get this setup. They just wanted to know the IP address that would be the source IP address for outbound SMTP connections and the name my machine sends in the HELO (or EHLO). I use a masquerade name so that the actual machine name isn't set, but that's OK because Internet SMTP servers don't care what the actual machine name is. Within 24 hours the rDNS was in place on Verizon's DNS servers and outbound mail started working.
That's it. Everything worked and all ISPs are accepting out mail again. Changing ISPs isn't always fun and it's never easy, but once everything is in place, everything will work like clockwork again.