How do I fix "501 Syntactically invalid HELO argument(s)"?

Question

I'm using exim on both the sending and relay hosts, the sending host seems to offer:

HELO foo_bar.example.com

Response:

501 Syntactically invalid HELO argument(s)

Answer 1

Possibly a problem with underscores in the hostname? http://www.exim.org/lurker/message/20041124.113314.c44c83b2.en.html

Answer 2

Underscores aren't actually valid in internet host names, despite some people using them anyway. A sane DNS server should not allow you to have records for them.

Change your system's host name so it's valid, hopefully this will fix it.