Our current implementation is similar to this, bit if the sender deletes a message, don't the recipients have a right to retain a message that was sent to them? For their own records I mean. This is what's causing the difficulty. A sender's right to delete the message vs a recipient's right to keep copies of messages sent to them.
They are stored on our servers. The problem is, not all users will want the message deleted just because one of the recipients does. This creates a conflict with the GDPRs right to have information deleted. Recipient A might want the message deleted but recipients B and C may not