Exchange undeliverable messages on reboot

My boss has been complaining (yikes) about sending mail to a particular business associate.  He said sometimes works, sometimes not.  If he uses his external google account, always works.

I was going to start troubleshooting, but I happened to be rebooting servers yesterday and when I rebooted Exchange 2003, I got the following returned message from several weeks ago:

Your message did not reach some or all of the intended recipients.

      Subject:      RE: Strange and unusual plant
      Sent:      10/10/2008 3:12 PM

The following recipient(s) could not be reached:

      'Matt XXXXXXX' on 11/2/2008 1:34 PM
            You do not have permission to send to this recipient.  For assistance, contact your system administrator.
            < #4.7.1 smtp;451 4.7.1 Greylisting in action, please come back in 00:05:00>

In addition, my boss got a bunch of returned messages (when I rebooted the server) for the person he said he had been having trouble sending to.  All the samples he sent me had the same error message such as follows:

From: System Administrator
Sent: Sunday, November 02, 2008 1:34 PM
Subject: Undeliverable: RE: Green Postcard

Your message did not reach some or all of the intended recipients.

      Subject:      RE: Green Postcard
      Sent:      10/13/2008 2:03 PM

The following recipient(s) could not be reached:

      'STEVE XXXXX' on 11/2/2008 1:34 PM
            Could not deliver the message in the time limit specified.  Please retry or contact your administrator.
            < #4.4.7>

I've read a couple of things about GlitchRetrySeconds or possible greylisting exchange bug, but not enough info to say whether that's my problem or not, and how to fix it.  
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Check this out: . Also you can finetune the retry options in exchange.
Options that should fix it:
- Glitchretry: and a howto:
- Use a smarthost (from your isp) for that one specific domain
- Restart SMTP services every x hours in a scheduled tasks (not advised but it should work)
Brian_MBAuthor Commented:
I'm starting to think I have multiple issues here and not just one.  
I had previously looked at KB934709 as you mentioned, but is specifically states:
Note This article does not apply to Windows 2003 servers that are running Exchange 2000 or Exchange 2003. This article applies only to Windows Servers that are running the SMTP Service without Exchange 2000 or Exchange 2003.
So I ignored the article.
So I'm left with 3 things(actually 4 now):
1.   The one greylisting message which I guess adjusting th glitchretry might fix.
2.  The several "Could not deliver the message in the time limit specified".  These were all to the one email address my boss says he can't send to.
3.  The fact that we got all of these NDR's upon reboot of the machine.
4.  And my latest quandry.  I used mfcmapi.exe to see if anything stuck in the SMTP temp tables, and to my surprise I have 0-19 folders and about 520-526 messages in each one.  Most dated 9/23/07 or 9/24/07, a couple dated 5/14/07.  Today is 11/05/08.  Why are these messages here and what should I do with them? Delete the messages? Delete the folders?
Are these issues related or separate problems?
I came across M$ KB 950757 and was thinking of trying this.
Of course I'm probably wasting my time, as I hope to migrate to Exchange 2007 before the end of the year.  

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
KB 950757 Seems like a very good idea. The get more info on the time limit messages, enable SMTP logging with all options to see what's going on. I don;t have experience with mfcmapi.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.