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)
Possibly a problem with underscores in the hostname? http://www.exim.org/lurker/message/20041124.113314.c44c83b2.en.html