If you are using Exchange 2003 then you may have experienced the greylisting bug.
This is the issue where messages disappear from the queues only to reappear as Non Delivery Reports when the server or the SMTP Server Service is restarted.
At last, Microsoft have released an update for this problem which is described here:
You can also download the hotfix from that page.
Hopefully Microsoft will push this out via Automatic Updates/WSUS soon so that more Exchange 2003 servers will not suffer from this problem.
At last Microsoft have released an official method to maange Exchange 2003 from Windows Vista. No more copying DLLs around and generally hoping for the best.
Although using Terminal Services to connect to the Exchange server is still the best way to do it, and is what I continue to do.