Message system - delete message, or flag for deletion? I'm wondering, what is the best approach about message deletion in a mysql based message system.

Plan A:
When the sender sends a message, it will be saved in 2 versions. One for the sender and other for the recipient. This way everyone can immediately delete his own message from inbox/outbox.
This approach has an advantage of immediately delete a row in database, but there are 2 time more rows for same number os messages, than the plan B.

Plan B:
The sent message is saved once, the sender and recipient see the same message. They only mark that row for deletion and a cron job has to delete only those rows, that are marked by everyone for deletion.
Advantages: only one row/message,
Disadvantages: messages are deleted rarely, because they need to be marked by two users.

Are there other advantages/disadvantages for these plans?
Is there a better way to do this? The goal is to make a fast system, optimization for speed is significant.
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.