Email being sent again when SMTP service restarted

I am getting the below problem on our clients SBS 2003 fully patched and updated servers and also our own which we need to resolve. If the SMTP service is restarted around 10 mails per User that were already sent by the users are sent again. The recipient then complains that they got the email twice and one 2 weeks or whatever late. It is not the exchange 2003 sp2 grey listing problems since usually the recipients dont use grey listing. I have also checked that different messages that have been resent and those that have not is that the latter has a first line in their message history in the Exchange Tracking Tool that reads "smtp store driver: message submitted from store" whereas the emails that are resent dont? Please help me.

You can try to use the Mfcmapi.exe utility to view and work with messages in the SMTP TempTables in Exchange 2000 Server and in Exchange Server 2003 that describes how to use the Mfcmapi.exe utility to view and work with messages in the Simple Mail Transfer Protocol (SMTP) TempTables in Microsoft Exchange 2000 Server and in Exchange Server 2003. Follow the link here - http://support.microsoft.com/?id=906557