I’m not sure what version of Exchange you’re using. But there are some tools for Exch2003 that are helpful that I recommend. Also, what is the exact error in the logs and/or bounced emails? What does your internal DNS show for the mail.xxx.com site you’re trying to send to? What does an external DNS server show for that same site?
1. SmtpDiag.exe from MS, download and run this at the cli on your Exch server. Very useful.
2. Exchange System Manager > Tools > Message Tracking Center