We were getting this error in the submission of one of our outbound Marketing forms.

Activity id: e1ede147-efb6-457d-bc19-826c6176a2e4, Request id: jH7xRiEzGFTdZQTbE2fkh9_Z_WtjumCqJERuYZbGSL0_0, Exception: Entity ‘Contact’ With Id = 896b960d-c5d7-4c4d-95c7-a9e226afbf8e Does Not Exist
The form had only the Lead form matching defined and Only leads for Update contacts / leads.


So here because of some earlier multiple/different form submissions, a contact got created and stored in the browser’s cookie, which CRM was referring to, and trying to set a Parent Contact for the lead record even though we were having Only leads set for update contact/leads option.
This is the behavior of the product.
https://learn.microsoft.com/en-us/dynamics365/marketing/marketing-forms#createupdate-leads-only

The solution is to delete the cookie or try in incognito or in-private mode or a different browser, and it would work.
This would probably arise because while setting up marketing forms we would do multiple submissions with test data for testing.
Hope it helps..