If a particular message has three recipients, then it will have three entries in this table. The 'deleted' column is a boolean that is initially false. But when a recipient deletes their copy, 'deleted' becomes true and the message will be hidden in the UI for that recipient only.
If it's the sender who is deleting the message, then just delete it in the Messages table, and no one else will be able to view it.
Depending on whether it's targeting businesses or consumers, expectations and needs are different.
No. There is no "right to retention" in the GDPR. Users have the right to access any data you hold that relates to them (with some exceptions), but you are under no obligation to retain data. GDPR requires you to do the exact opposite - delete (or thoroughly anonymise) data as soon as possible.
Art.5(1)(e) says "Personal data shall be kept in a form which permits identification of data subjects for no longer than is necessary for the purposes for which the personal data are processed". If you're aiming for maximum GDPR compliance, it would be sensible to delete the messages from your server as soon as they have been delivered to the recipients. You're a messaging service, not an archival service; storing the messaging data or metadata indefinitely is contrary to the principles of the GDPR and exposes you to liability if that data is ever leaked.
I'd also question why you need plaintext access to user messages in the first place. End-to-end encryption protects you and your users. If you can't access the data, you can't inadvertently breach the GDPR.
As for the GDPR: The GDPR applies to "personal data". A user's email is certainly personal data. But if someone says a person's name in an email, that is also personal data.
Your problem is you have to either cover everything under consent or use legitimate interests and weigh -- ie conduct a balancing test as (very hand-wavingly) specified by the GDPR -- the balance between a data subject requesting a deletion's right to privacy and the legitimate interests of the other message recipients in retaining messages. A privacy lawyer can help walk you through doing this. Your other alternative is, if you have a lead regulator, directly reaching out to them and asking for guidance. If you haven't, or can't, establish a lead regulator you may try the ICO. They've staffed up in an effort to be the one stop shop of choice, though the UK decided to leave the EU so who the hell knows what's going to happen. Alternatives include ie / DPC.
In particular, A17 specifies:
NB: A6.1.a is consent.
> (1) The data subject shall have the right to obtain from the controller the erasure of personal data concerning him or her without undue delay and the controller shall have the obligation to erase personal data without undue delay where one of the following grounds applies:
> a) the personal data are no longer necessary in relation to the purposes for which they were collected or otherwise processed;
> b) the data subject withdraws consent on which the processing is based according to point (a) of Article 6(1), or point (a) of Article 9(2), and where there is no other legal ground for the processing;
So your path seems somewhat straightforward: remove the link from the deletion requester to the message, and make sure your statement of purpose in the consent says that you will delete iff all recipients request deletion. This does mean you need to carefully write your GDPR consent forms for your service, but see lawyer bit above.