The Problem: All email that you send get’s bounced back with the following message:

Subject Line: Delivery Status Notification (Failure)
Message: Delivery to the following recipient failed permanently:
user@domain.com
Technical details of permanent failure:
The following message to <user@domain.com> was undeliverable.
The reason for the problem:
5.1.0 – Unknown address error 550-‘Access Denied’
A problem occurred while delivering this message to this email address. Try sending this message again. If the problem continues, please contact your helpdesk.
domain.com gave this error: Access Denied

The Cause: There is no “mail.domain.com” in the dns system.  In my case I was sending the mail via an alias (it was a notification email from the web server).  The receiving mail server sees the email as forged and bounces it.

The Solution: Go to the dns system and create a mail.domain.com and point your MX records to that.  It’s a bit silly, but it has to be done that way.