Exchange Error: 451 5.7.3 Cannot achieve Exchange Server authentication

While planning to decommission our old Exchange 2010 environment we had to change the CAS/Hub Transport IPs because we needed to reuse them for some of our new SMTP relays - we have quite a few (way too many) relaying servers that use IP instead of SMTP hostname.

After changing the IPs, the Transport Queues filled up with the following error:

451 4.4.0 Primary target IP address responded with: "451 5.7.3 Cannot achieve Exchange Server authentication." Attempted failover to alternate host , but that did not succeed. Either there are no alternative hosts, or delivery failed to all alternative hosts.

This affected all internal mail, because the Exchange 2010 servers are still routing to our 2013 environment.

The problem was easily overlooked, but the fix was simple as well:

On your new environment (the servers you are sending to) check your relay connectors and make sure they do not include the IP address or subnet of your old environment (the servers you're sending from).

You might have to restart the Transport Service on the old servers, but the queues should now start emptying out.