Exchange 2003 sp2 and greylisting...
Exchange 2003, you say? Who is still using that? 
Most people are.
I've done the research a couple of times now, so I wanted to write it down in one place. Of course, I decided to share it with you as well.
Exchange 2003 with service pack 2 has some interesting challenges when sending e-mail to another SMTP server when that "other" server implements greylisting.
Sidebar: Greylisting is an anti-spam measure. Most of the programs that actually transmit e-mail spam don't fully follow SMTP protocols. If an unexpected SMTP protocol result is received, then they drop the SMTP connection and move on to the next one. A server that is using greylisting maintains a cache of the IP addresses of servers that have sent good e-mail. When a new server connects for the first time, the greylisting server sends a SMTP protocol message that says "I'm busy - come back in a little while" - with the expectation that the message will be retried with in a few minutes.
Most spam mailers will just drop the message.
Sometimes, Exchange will somehow seem to lose the message. Yep, lose it. It doesn't show in any visible queue, it doesn't generate an NDR, etc. etc. It just seems lost - until you restart the SMTP service (generally by rebooting the Exchange server for your monthly patch updates). Then, you may get a gazillion NDRs suddenly generated from messages that were sent quite some time ago...and users start asking questions.
This can also happen with the default Windows SMTP service, after applying Windows Server 2003 service pack 2.
For Windows Server, there is a hotfix available:
On a Windows Server 2003-based SMTP gateway server, some messages may remain in the queue folder until the SMTP service is restarted
http://support.microsoft.com/default.aspx?scid=kb;EN-US;934709
For Exchange Server, your best bet is to both apply the above hotfix and to change a registry parameter known as GlitchRetrySeconds.
For a great explanation of GlitchRetrySeconds and what it does (as well as lots of other information about the SMTP queueing engine), see:
Explaining the Mysterious SMTP Advanced Queuing Engine
http://msexchangeteam.com/archive/2005/04/04/403297.aspx.
But all you really need to know is to increase the value. I personally like the value of three minutes (180 seconds). Other people prefer two minutes (120 seconds). The default value is one minute (60 seconds). Since messages are retried three time before they are actually "sent to the back of the line", one minute can be too short (a typical greylisting delay is five minutes [300 seconds]).
The downside to setting GlitchRetrySeconds too high is that it can cause a high-volume SMTP server to not send as many messages. This is rarely a problem for most installations. But because of this, the Exchange Server Analyzer Tool will report on a non-standard value for GlitchRetrySeconds:
The SMTP GlitchRetrySeconds registry value has been manually set
http://technet.microsoft.com/en-us/library/aa996601.aspx
And finally, here is how and where you modify the value:
How to Configure Glitch Retry Interval in Exchange Server 2003
http://technet.microsoft.com/en-us/library/8b43be56-48e6-400b-8014-54c95f87d1de.aspx
Whenever I hunt for the above article, it always takes me a little while - because of the difference between "interval" and "seconds" in the article title and in the registry value. Ooops. 