let me start by saying I am not familair with Exchange 2007.
A client of mine is running SBS 2008 and Exchange 2007. Under Server Cnofig Hb Transport - I see 2 Receive connectors that allow you to change the HELO message to a FQDN. Both are cofigured for the local FQDN. One is labeled Client and the other Default. I am able to change rthe Client connector to something like mail.companyname.com but not the Default. If I were to restart Exchange, would this produce the desired effect of changing the HELO message?