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

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)

From stackoverflow Ranguard

• grep, although I'm not good enough to come up with the proper re, anyone else?

  From Bill K

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

  Ranguard : On the smtp relay server run this and restart exim4 echo 'helo_allow_chars = _' > /etc/exim4/conf.d/main/04_exim4-helo_hack
  From benefactual

• 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.

  From MarkR

• The argument to HELO should be a hostname or an IP address. foo_bar.example.com is neither an IP address nor a hostname (underscores are illegal in hostnames), so the error message is correct and there is nothing to fix.

  From Jörg W Mittag