Last weekend, our entire network was moved to a new facility.
In the process, all of my servers received new internal IP addresses, but we moved the appearance our public IP subnet to the new facility, so all servers retained their DNS-resolved external IP addresses.
We also installed new firewalls. These received a different public IP address than the previous firewalls.

For the last two days, a number of my users have received refusal notices from the email system of several of their collaborators.
Not all of them, but some major ones; AOL, the local Road Runner system, Comcast and others

The GWIA log shows entries such as the following:
11:13:38 25F MSG 2197902 Command:
11:13:38 25F MSG 2197902 Response: 554 5.7.1 - Connection refused. IP name lookup failed for

10:31:24 25F MSG 2197609 Response: 550 IP is blocked by EarthLink. Go to for details.

Here's the odd part:
The address noted in the error messages is not the public address of my GWIA.
It's the address that the previous firewall used!

Most of what I've found on the internet refers to either non-existent PTR records for the domain name, or the IP address being placed on an RBL.

A check of that particular IP address on results in no entries in the 104 RBL's they monitor, and the actual IP address for my gateway has a valid PTR entry

So, I don't think that this is a GWIA problem, per se, but I'm wondering if anybody has any ideas as to the cause of the issue.