RE: What does "Contact deleted" mean in Marketing-Email Insights?
Hi Simon,
I have tried to reproduce your issue but no luck.
Test 1: I changed contact's firstname and lastname and email address by opening subscription center in first email, then the contact was removed from segment due to he no longer met criteria,
but second email could be still delivered to the new mailbox, and Dynamics still recognizes contact with new information as previous contact record.

Test 2:
Once the customer journey went live, I deleted member in segment.

However, Insights data still show that email has been delivered, meanwhile the Contact name value became empty.

In a word, my tests are based on definition of the interaction "Contact deleted", currently I couldn't make progress by following its description.
You could wait for some time to confirm whether the issue would be a temporary bug if contact who has this interaction in her timeline could still receive email for her,
or open a support ticket for better help.
Regards,
Clofly