"Access denied - Invalid HELO name (See RFC2821 4.1.1.1)" messages in exim_mainlog

Symptoms

When sending an email to a remote server or receiving an email from a remote server, the reciving server's response will contain the following:

Access denied - Invalid HELO name (See RFC2821 4.1.1.1)

Description 

The receiving mail server will send an "Invalid HELO name" message when the sending server's HELO message contains a hostname that doesn't resolve to the sending server's IP address or the PTR record for the sending server's IP address doesn't point to the hostname in the sending server's HELO message. The receiving server can also send an "Invalid HELO name" message when it is unable to resolve the hostname in the sending server's HELO message to the sending server's IP address or cannot retrieve the PTR record for the sending server's IP address.

Workaround

For the sending server, ensure that the hostname sent in HELO messages resolves to the server's IP address and that the PTR record for the IP address points to that hostname.

For the receiving server, ensure that the server is able to resolve hostnames.

Additional resorces

Who manages the PTR records for my IP addresses?

What nameservers should I use in my resolv.conf file?