You really ought to talk to counsel. I founded a startup, and the thing I didn't know before I did that is lawyers will front you legal fees. A typical arrangement with a good valley law firm goes like this: they agree to front you $15-$20k in legal fees, payable immediately upon a raise exceeding $500k. They won't front you cash they have to pay out, ie you'll have to pay filing fees or other stuff, but the majority of your expenses will be legal time. This fee arrangement isn't necessarily available to any random, but if you can get a warm intro to a startup partner at a good law firm (Wilson Sonsini, Gunderson Dettmer, Cooley, etc) you may be able to get this arrangement. Of course, they're not necessarily going to hand it out to anyone who asks.
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.