I had the same problem that was mentioned here before:
http://groups.google.com/group/microsoft.public.exchange.admin/browse...

For those who doesn't know - greylisting is used on some mail servers to
tempfail first attempt of an email, asking the sending server to retry later.

In short (more details will follow) - 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.

I have just openned a PSS case about this and working with Microsoft.
However this issue is not easy to re-produce, so I would like to get
feedback from you as well.

My questions to you -
Have you encountered similar problems, such as users complaining that they
got NDR for a message they sent 2 weeks before, or that the recipient calls
them and tell them "why did I got now and email you sent a week ago?"
(And you find out that the recipient server uses greylisting).

Meanwhile I have found those workarounds and currently I don't have the
problem, but it still needs further investigations:

Workaround 1: Send emails to greylisting domains via an ISP Smart Host
(using SMTP connector).

Workaround 2: Use scheduled tasks to restart SMTP service every day.

Workaround 3: Change SMTP virtual server retry timeouts (this does not seem
to help but I changed it anyway to values you can see below).

Here is a more detailed report that I have also sent to Microsoft PSS:

When sending outgoing email to mail server that implement greylisting,
sometimes Exchange retries the message later (as expected),
but sometimes Exchange simply does not retry delivery ,
and neither sends NDR nor Delay notification to the sender.
Two weeks later when I restart the SMTP service for installing security
updates (such as IMF updates),
then Exchange tries again to send those "lost" messages.

The problem seems sporadic - sometime it works, sometimes it doesn't, with
the same configuration.

The problem appears with several different destination domains. The common
thing is that all of them use greylisting.

Description of the server
A single server with the following software:
Primary roles = DC + Exchange + File server.
Windows 2003 Standard SP1 (upgarded from win2000 about 1 year ago).
DC + DNS + FSMO ROLES (This is the only DC in the network).
Exchange 2003 SP2 with IMF configured and enabled.
Symatec Corporate 10.0.2 (file protection) + SMSMSE 5.0.1.208 (mail
protection).

Connection to the internet:
Cisco PIX 501 firewall ver 6.3(1)
ADSL line to the ISP (PPPoE).
ISP name = Bezeq International (www.bezeqint.net)

DNS settings:
The same server is an internal DNS server, and uses ISP servers as
"forwarders" .

SMTP connector settings:
Send using DNS (the default).

SMTP virtual server settings (related to the issue):
Logging = NCSA common log file format.
Delivery retry interval (I have change the defaults):
First retry = 1 minute
Second retry = 2 minutes
Third retry = 15 minutes
Subsequent retry = 30 minutes
Delay notification = 1 hours
Expiration timeout = 2 days

--
Yizhar Hurwitz
http://yizhar.mvps.org

----------------
This post is a suggestion for Microsoft, and Microsoft responds to the
suggestions with the most votes. To vote for this suggestion, click the "I
Agree" button in the message pane. If you do not see the button, follow this
link to open the suggestion in the Microsoft Web-based Newsreader and then
click "I Agree" in the message pane.

http://www.microsoft.com/communities/newsgroups/list/en-us/default.as...