Problems with email delivery to AOL.com after server move

When I moved a client’s Exchange server to a new location and new IP address, email to aol.com was bouncing back with:

There was a SMTP communication problem with the recipient’s email server.  Please contact your system administrator.
<mail.mailserver.com #5.5.0 smtp;550 RCPT TO:<userat@aol.com> Relaying not allowed – please use SMTP AUTH>

After a little research I found out that you can go to postmaster.aol.com and they have a checklist you can follow to resolve the issue. If you do move your server make sure that your ISP makes the IP Reverse DNS. You can check it at Reverse DNS Check.  You should also check and see if your new IP address is on a Known Spam List. The easiest place to check is Spamhaus. The most annoying part is that they are not a wealth of information about the server IP using their Reputation Check Tool.

After you do all that AOL asks you can open a Trouble Ticket. They might get back to you in a week.