System Undeliverables sent to users after a reboot

[anothracount]

I just recently rebooted our exchange server, and about 15 users recieved bunch of undeliverable messages that they had sent anywhere from 1-45days prior to the reboot. They all got the undeliverables as soon as the server was rebooted.
Can anyone give me any ideas where or what caused this.
I m wondering where and why they were waiting for a reboot.

 

[noveyron]

Could be that your AV is scanning where it shouldnt?

http://support.microsoft.com/kb/823166

 

[Topkapi]

I had exactly this issue last year. It was due to some receiving mailservers using greylisting as an anti-spam measure. Exchange doesn't handle this very well.

For me the solution was to send all email out via a smarthost which in my case was the SMTP proxy on my firewall.

Some other suggestions are listed here

http://searchexchange.techtarget.com/tip/0,289483,sid43_gci1269925,00.html

Hope that helps