The past two reboots (where the server has been offline for a while) has resulted in non delivery reports being sent back to some of the mailboxes for mail that was sent several weeks ago and that had not been reported as failed when the mail was initially sent.
The first time this happened I thought it was just one of those things, especially as I had not seen mail in the queue before rebooting the server. After the second occurrence I knew it was time to investigate.
SBSisyphus has a great posting including a link to the exchange2003 (sp2) patch that should fix the “kb950757 Email senders do not receive an indication that some messages have been held by Exchange Server 2003 until the SMTP service, The Microsoft Exchange Information Store service, or the Exchange server is restarted”. I applied it to my machine and I’ll have to see what happens.
For what it’s worth you do not need to reboot the server (unless wmiprvse.exe is running – but you get an option to kill this process if it is running before proceeding) but it will stop and start your mail and web services so don’t apply it during the day and it goes without saying that you should have a backup first.