We recently had a customer that switched Internet service providers. After making the switch, users were getting “sending delayed” messages from the Exchange server. The problem turned out to be caused by mis-configured DNS settings in the Exchange 2003 SMTP service. Some e-mails appeared to be going through fine, while others were delayed and eventually dropped. Sometimes, messages would go through, the other person would respond, and then they’d get a delayed notification for the originally sent message. After some e-mails that were sent to CoNetrix were completely dropped, I started looking more closely at the SMTP service configuration. I went through every setting and eventually found some entries for the old ISP's DNS servers buried in the following location: [more]
Servers -> SERVERNAME -> Protocols -> SMTP -> Default SMTP Virtual Server -> Properties -> Delivery tab -> Advanced -> Configure
This configure allows you to specify “external DNS servers”. Apparently, based on the name, someone thought the real “external” DNS servers should be used (instead of the local DNS service that uses the external servers as forwarders). I removed the old ISP server entries and replaced them with the external DNS servers of the new ISP as a test. Once I did this, e-mail started sending immediately. I then changed the entry to the local IP of the server (so the local DNS service would be used). Things continued to work. Setting those DNS entries is not part of our normal server setup procedures, so I'm not sure where the DNS entries originally came from. They may have been populated by some "wizard", so keep the SMTP DNS settings in mind if you ever have a similar problem.