Kilfarsnar:
The fact that you did a new install from scratch on different hardware with everything fresh except the DB's, takes me back to something breaking down in the receiving domains interpreting of some piece of information. Something different about the receiving domain's configuration, and how it's interpreting a piece of header information or something. I ran across the below pasted notes referencing msdIT's log error and the 501 Syntactically invalid HELO argument(s). This is not the problem in my case, but it may point to something else in the right general direction.
--------------Paste---------------
Syntactically invalid HELO/EHLO.
Description
The HELO or EHLO command is followed by the remote server's hostname. The domain passed with the command should be a valid one. This problem is most noticeable on Windows servers where they often configured with the same DNS name as their local 'windows' domain, which allow '_' to be contained within the domain. When the remote server issues an HELO or EHLO, it includes that same local windows domain name, rather than a syntactically correct, valid, hostname.
Note that while SMTP servers should not block mail with an invalid hostname passed to HELO or EHLO, many do. Although it is not technically breaking RFC's, the fact is that the [Sending] mail server is incorrectly configured.
----------End-Paste---------------
We have no underscores in either case, so this is not the exact issue in our case, but it makes me wonder if there's not something else that IS configured in such a way that the HELO is being rejected. I've verified our RDNS, so that's not it, I've verified we're not blacklisted by either the local receiving server, nor any of the blacklisting services. I can telnet into the mailservers I tested so I have to wonder if it's not something in the header information being stamped on the message. You guys actually seem much more knowledgeable about Exchange than I am so maybe this information will spark a thought on your end.
Question: in looking at the outbound log files on these messages, the message ID reads <message ID#>@<computerame>.
Computername is a valid computer name, but could the receiving side be looking for a differently formatted name (IE: a domain name, or comparing this name to a RDNS or something here?). Some of this may seem incredibly elemental to you guys, but I sort of inherited this in a one man IT department, so bare with me here..