I found out we were getting rejected by some servers because our hostname was setup incorrectly.
We had updated the host name to be a valid FQDN a long time ago in the Basic WHM setup, but we neglected to update it in the Network Setup.
I am going to call the new hostname: new.mynewdomain.com
The old hostname: old.myolddomain.com
[good] new.mynewdomain.com now resolves an IP successfully.
[good] when i type "hostname" on the server i get "new.mynewdomain.com".
[good] When i send an email to my personal gmail account, and check the headers, old.myolddomain.com is nowhere to be found, just new.mynewdomain.com.
[bad] When I send an email to an account on one of our other servers, it gets rejected that it can not verify the sender. When i look at the /var/log/exim_mainlog, it shows:
Why would the other server still be checking old.myolddomain.com?
no IP address found for host old.myolddomain.com