#501″FQDN” is invalid or DNS says does not exist

Undeliverable:
destinationdomain.com rejected your message to the following e-mail addresses:

Recipient (recipient@destinationdomain.com)

destinationdomain.com gave this error:
<EX01.doitfixit.local> is invalid or DNS says does not exist
A problem occurred during the delivery of this message to this e-mail address. Try sending this message again. If the problem continues, please contact your helpdesk.

Diagnostic information for administrators:

Generating server: EX01.doitfixit.local

recipient@destinationdomain.com
destinationdomain.com #501 <EX01.doitfixit.local> is invalid or DNS says does not exist ##

To fix the issue open Exchange Server Management Console and open internet send connector properties. (Organization Configuration -> Hub Transport -> Send Connectors -> <Send Connector> specify the Mail FQDN.

Restart “Microsoft Exchange Transport” service.