For several years I received this type of complaint. Every time I researched the problem I found problems with DNS. Lack of PTR record, MX record in error and ultimately a lack of SPF record. . It's not Domino fault! It's not my fault!
The fault is always (or almost 99%) the network administrators or DNS administrators.
I use the following in my own DNS to avoid problems:
1 - Use the A record pointing to your Domino Server
2 - Create a PTR record for your Domino Server
3- Create a MX record and setup it pointing to the A record of your Domino Server.
4 - Create a SPF record
Test tool: Mool BXTox