Had a user having problems sending an email to an email address.  By all appearances the rejection notice seemed to point to an issue of our mail server having problems getting to their mail server.
I told the user to try it again later (this and telling them to reboot fixes most issues).  Still more rejections after a couple of days.
So I Googled the error and found the fix on the second link that showed up.

The problem was actually a malformed contact in the user’s Microsoft Outlook contacts.
By copying and pasting the email address into notepad and then back into the contact it was fixed.
The issue stems from the email address that was stored in the contacts had mailto: and some other weird characters even though what was displayed looked just fine.

The other thing I did was to clear the auto address that pops up in the to field when composing a new message to make sure it was getting the address from the newly fixed contact.