At last… I found the needle in the haystack. Wow, what a pain. We got our new email server all configured about 10 days ago, and it seemed to be working great for just about everyone. However, no one from with an aol.com email address was getting our emails.
After many many hours of searching I finally traced down what the issue was. This forum post from tek-tips.com was very helpful.
AOL required reverse DNS to be configured for the IP address that is sending the email messages.
This had all been configured correctly with our old email server, but when we migrated the the new email server, I had to change some of our firewall settings. The email server happens to accept request from a couple different IP addresses. So it was successfully receiving emails that were routed through mx1.checkoutmycards.com, but when it was sending emails it happen to go out through a different IP address.
I realized this by doing a “What is my IP” search and seeing that it didn’t match mx1.checkoutmycards.com. All I had to do was change one firewall setting so that outgoing emails got sent through the same IP address as the one that had reverse DNS configured.
I even created an @aol.com email address just to test the scenario and make sure things worked. Hopefully all of you at aol.com can now receive our emails.