We have had a similar issue with a client. The problem comes from McAfee av on the exchange server causing the corruption. Turn off the server side and ensure all clients are running av.
Have you tried disabling antivirus on the server?
On the client?
Have you disabled the Symantec Mail Security and Antispamming?
Can you try these and post back what happened when new mail arrives in each of the states?