Ran into this error today on a server. Some mails got through but some was not getting through.
Check that /etc/hosts has a FQDN (fully qualified domain name).
Also check the size of the mails being sent, in my case the issue was that mail was to large for the receiving server thus this error message was produced at the sender.