I am having some problems with emailing to a couple of specific gmail addresses, but not all gmail addresses. I'm running Exchange 2010. Here is the error:
Diagnostic information for administrators: Generating server: [email protected] # #MAILTO# Reporting-MTA: dns; EXCH Final-recipient: X-MAILTO; [email protected] Action: failed Status: 5.4.0
Errors like these are usually problems related to DNS resolution.
Try to run nslookup locally on your exchange server:
set type=mx gmail.com
Look at the results (run the gmail.com query several times), and see if stays coherent. Check with an outside client against a different DNS server and see if it matches.