Sending emails to email address outside of my network

I do have DNS and an internal exchange server that can send outbound

This is not a email issue per say its the dude that gives me the error message when i try to send to any domain other then the one that i have mapped.

ITs really weird

It happens when i set up an email notification to my cell phone