[Pkg-exim4-users] 550 Access denied - Invalid HELO name (See RFC2821 4.1.1.1)

[Robert Steinmetz]

I am having trouble delivering mail to one server. All mail is rejected 
with the above error message. The message seems to indicate the 
receiving server is requiring strict RFC compliance and I am failing the 
reverse DNS lookup. But I'm not sure exactly which response it is 
expecting. I assume the name associated with the MX record, but the 
machine also has several DNS entries for different functions.

The receiving server is running ESMTP Exim 4.82

I am running ESMTP Exim 4.76 on Ubuntu 12.04. My configuration is in  
/etc/exim4/conf.d

I have searched the web and tried a couple of things

I edited update-exim4.conf.conf and added

hardcode_primary_hostname='smtp.mydomain.com'

I added MAIN_HARDCODE_PRIMARY_HOSTNAME = smtp.mydomain.com to 
/etc/exim4/exim4.conf.localmacros

I ran update-exim4.conf and restarted exim4.

/etc/exim4/conf.d/mail/02_exim4-config_options contains the line 
primary_hostname = MAIN_HARDCODE_PRIMARY_HOSTNAME

/etc/exim4/conf.d/mail/02_exim4-config_options contains the line 
smtp_banner = smtp.mydomain.com ESMTP Exim $version_number $tod_full

  The problem remains.

I'm obviously overlooking something but I wonder what it could be.