this sounds like a connection record or domain document issue rather than DNS otherwise a NDR would be returned from the outbound gateway SMTP server.
Look at your address book and see how the system is routing mail to the gateway server.
The method I have used is to have a Foreign SMTP domain document that is called TheInternet and points to internet domains *.*
A connection record on the gateway server of type = SMTP, source = gateway server, destination domain = TheInternet, connection type = direct.
Make sure you have a connection record from your mail server to your outbound SMTP gateway server that uses NRPC.
All servers should see the connection record on gateway server and route mail to that server for onward routing.
If using this system, refresh or recreate the domain and connection records in case of curruption or some other error.