Email messages resend when Exchange is rebooted

I’m running exchange 2003 sp2 on win2k3 svr sp1.

When I reboot the server I’m getting reports that a varying number of emails are being resent. These messages were originally delivered to make things difficult. The last time I rebooted the server I checked that the queues were empty and again a handful of messages were resent (external outbound emails only).

I’ve tracked it down to users in a particular mailbox store only. Other users in different mailbox stores don’t experience this issue.

Tons of pressure on this problem because some of the emails are purchase orders for ?50k +.

Any help greatly appreciated.