When customers were trying to e-mail us they were receiving the above error back.
Delivery has failed to these recipients or distribution lists
Your message wasn’t delivered because of security policies. Microsoft Exchange will not try to redeliver this message for you. Please provide the following diagnostic text to your system administrator
After a little investigation. We have a mailbox which forwards the e-mail to an distribution group. On the distribution group the Require that all senders are authenticated option was checked. Unchecking this resolved the issue.