Handling a chat room in a database
The following is kind of a shot in the dark in lack of clarification of the question, but as I had built it already earlier I'll post it in absense of any other answers.

How about implementing the message-deletion-per-recipient so that you only keep track of those messages that have been tagged as deleted-by-recipient? That would translate into getting rid of the recipient table as you had it and instead having a recipient table plus a cross-ref table for deleted messages:

recipient table

| recID              |
| recipientID --FK   |


deletedmessages table

| msgID --FK         |
| userID --FK   |


When fetching messages to be displayed to a given recipient, it would be enough to either join the two tables on msgID or to do something like

... WHERE NOT EXISTS (SELECT 1 FROM deletedmessages dm WHERE dm.recipientID = &lt;current_user_ID&gt; AND dm.msgID = m.msgID)


to filter out the deleted ones. Having deletedmessages indexed by both columns (probably mandatory to get the foreign keys references properly set up) would allow the DB to execute this very efficiently.

This way deletedmessages would only grow when a user actually deletes a message and not grow that much.

There's a SQLfiddle with the above solution.