Microsoft Exchange 2003 with queued, outgoing email that was not released until server restart

We currently host mail for several customers using Microsoft Exchange 2003 running on Microsoft Windows Server 2003, Enterprise Edition.  Last week, we rebooted the server to address a separate issue.  It appears the restart caused a set of messages to be successfully processsed that were originally sent over a two month period.  These messages were being sent from our server out to 10 - 15 recipients.  Several of the recipients emailed back that they had just received the email and noticed that they were originally marked to be sent in August.  These messages were being sent to 5 - 10 domains and the domain has not been blacklisted. During this period (the server had not been restarted in 78 days), we had successfully processed thousands of incoming and outgoing email.  Email is core to this customer's business and  they must be notified immediately if an email is not sent or rejected.  Does any know what could cause this behavior and what should be done to better monitor/prevent it from happening again?