I have had a user unable to send external e-mails, getting the following error message from exchange:
The message could not be delivered because the recipient's destination email system is unknown or invalid. Please check the address and try again, or contact your system administrator to verify connectivity to the email system of the recipient.
<mail.domain.local #5.1.2>
However, another user has no problems sending to the same e-mail address.
They have tried a number of times to send the e-mail...
I did have a quick google and make sure the domain name they are sending to resolves on the exchange server - not sure what else to look at...