Message system - delete message, or flag for deletion?
Ultimately it will depend on where you want the responsibility for deleting the emails to reside, system or user? If your main goal is performance then the fastest way to do this would be to only store a single copy of the message and then send the clients a reference to this message instead of the message itself. The client can then download the message when a user clicks on it. Once a message has been downloaded by all recipients then it can be flagged for deletion by the system regardless of whether the clients decide to delete their local copy or not.

I would look at how other messaging systems work and decide whether the method they use suits your purpose. For example Microsoft Exchange uses Single Instance Storage, a description of this is below:


  Exchange utilizes what Microsoft terms a single-instance message store. This single-instance message store works on a per database basis. What does this mean? If an e-mail message is sent to multiple mailboxes that are all in the same database, the message is stored once and each mailbox has a pointer to the message. The transaction is also logged in the transaction logs for the Storage Group that contains the database. However, if the e-mail message is sent to multiple mailboxes that are located in different databases, the message is copied to each database and written to the transaction logs for each Storage Group that contains the database with a copy of the message. 


As the designer of the system it is ultimately up to you to make the call based on the requirements you are given. That being said, my personal preference is to put the ownership on the clients to tidy themselves up so that you can worry about important things instead. You could implement some type of archiving system if you wanted to so that once it is downloaded by all clients it gets archived for a set period of time before being removed - maintaining a good backup strategy is also important in these scenarios.

Remember, although speed is important you can only go as fast as your network allows you to under a given load - something a lot of companies seems to overlook. 

I hope this helps you.