I have seen this problem a couple of times over the past couple of years and today I saw a newsgroup posting on it so I figured it was blog-worthy. :-)
Some SMTP services (not Exchange) check the validity of the FQDN that is sent to them by an SMTP client. If the FQDN that is being sent includes an underscore character (_), then they will reject the message. Exchange will keep trying (for 2 days by default) to send the message, then it will NDR it to the sender, but no really good explaination. The only reason I figured this out the first time I saw it was because I put NetMon on the server and watched the SMTP conversation.
So, if your server name is something like EXCHANGE_1 and the domain name (internal) is something like SOMORITA.LOCAL, then Exchange/Windows SMTP will send an SMTP HELO or EHLO that looks like this:
EHLO EXCHANGE_1.SOMORITA.LOCAL. Most SMTP systems are tolerant of this and accept the connection anyway. Some firewalls and Unix-based SMTP systems enforce do reverse looks to ensure the domain name is valid or they rigidly enforce the DNS standard and thus will reject the connection. I wish I had versions of these Unix systems or firewalls, but I don't.
If you have a
single Exchange server, you can easily fix this without renaming the Exchange server. (Renaming an Exchange server is ugly, ugly, ugly. Don't do it!) Go to the properties of the default SMTP Virtual Server, look at the Delivery tab, click the Advanced button. You will see on this page the Fully Qualified Domain Name. Change that name to something that is properly resolveable from the outside, such as
SMTP.SOMORITA.COM, where that is the name that can be resolved from the Internet. Just make sure that you remove that underscore character.