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

<pre><code>HELO foo_bar.example.com
</code></pre>

<p>Response: </p>

<pre><code>501 Syntactically invalid HELO argument(s)
</code></pre>

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