Hi there
We use mostly Entourage and a few clients using Mail. We're not running with Exchange Server but we've had similar problems to those you describe, with messages getting duplicated. This and other wierd behaviour often followed by total crash of the clients mail application.
Users often suspect the server, or viruses, but in every case they just let their mail database get too big. There is a limit to how large the Entourage database can get before total chaos sets in. And the application never warns the user that disaster is about to occur!
There is a service pack you can download which increases the file limit, but to try and solve your problem you need to restart Entourage holding down the Option key. This has been a helpful article for me on several occasions;
http://www.macdevcenter.com/pub/a/mac/2002/06/04/entourage.html
Rebuilds have more often than not sorted our problems out. Once the user can get back into the mail app wihtout it doing anything strange, they can archive their mail and everything is fine again. Until the next time!
In severe cases rebuilds wouldn't work and I've had to go to a tape backup and restore an earlier copy of their Main Identity folder. Hopefully that won't be necessary.
Every case of Entourage or Mail doing wierd stuff for us has been datafile related. Some users were archiving folders by moving them to their hard drive, but didn't then delete the folder from the mail app. Your problems may be related to the Exchange Server, but I thought I'd post this in case.
Good luck.