I'm curious why you don't use a more relational system for storing the e-mail content in exchange...
Surely you could store a message sent using exchange that went to X users on y servers just y times - or once if they all used the same storage?
You would only need to store the details about who it was delivered to, resulting in a performance increase an order of magnitude as you'd just be saying "this user got a copy of this message". You wouldn't need to store a P1 header except for those users outside of the exchange environment - the list of who got the message is available in the datastore already. Deleting messages becomes as easy as altering a record in the DB to say that it's deleted and if all references to a message are deleted add it to a list of messages to purge from the system whenever a purge is done.
It would result in dramatically less use of storage, less inter-server bandwidth and faster message access.
To support saving changes to the message you could easily either create a new base message or a delta based on the original - which would again be more efficient...