How to fix Greylisting Emails with Exchange 2003 sp2

Problem:
It looks like there is an obscure problem with exchange server 2003 with service pack 2 sending to a server that is using greylisting.

Greylisting is a technique that can be implemented on a mail server to reduce spam.  The concept is that the mail server is set to temporarily reject the initial connection attempt and to tell the sender to resend the email.  This second connection attempt is then accepted.  The idea is that spammers will not send this follow up email, thus reducing spam.  The sending user would receive a rejection notice that states: “You do not have permission to send to this recipient.  For assistance, contact your system administrator” or  “Recipient address rejected: Greylisted for 5 minutes”.

Also when you restart a server, emails will start to blast out from the past, which is another symptom of this problem (restarting a server will restart the information store service).  This Microsoft Technet question describes what is happening well:

(http://social.technet.microsoft.com/Forums/zh/exchangesvradmin/thread/8c27e334-f9d1-4ecb-9a5d-72dd5ba1224f)

In short- Exchange 2003 SP2 failes to re-queue messages sent to some servers that implement greylisting.

This does not happen all the time (some messages go through but sometimes it fails).

When the problem happens, those emails are hidden in some kind of a black hole, and the sender does not get an NDR nor Delay notification, even after those timeouts expire.

Such messsages can remain "lost" for days or even weeks, until the SMTP or Information Store service is restarted.
 
After a restart of SMTP service, Exchange suddenly finds those lost emails (I guess they were in the Mailbox Store), and retries to send them or returns NDR to the sender.

Solution:
Fortunately Microsoft has created a specific hotfix that will address this issue. More details of this fix can be found here http://support.microsoft.com/?kbid=950757 

There are other users that have reported that the registry fix will work as well:

Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SMTPSVC\Queueing]
"GlitchRetrySeconds"=dword:00000078