My suggestion is:
Do not allow email changes in the relevant field directly;
Set up a separate "changeToAddress" field to enter a new email address; Consider this a change request, not a change.
When that field is filled out, send a transactional email to this "new email" address using a dummy key in Marketing Cloud (use GUID() / newId() functions) with a button for the recipient to confirm the change. It makes sense to include the contact ID in order to be able to never lose the connection to the "right" contact in the next step.
set up a handler page that handles the confirmation of the change request. you can directly change the "real" email address field in this step using updateSingleSalesforceRecord and the contact Id. On this page you can also update the record on all subscribers, to prevent that it could get out of synch with SFSC, as this is not directly tied, which leads to the effects you describe.
after some time , delete the dummy key that was used for the transactional send using Contact Deletion framework.
If nochange confirmation was given, you can also empty the email address from the "changeToAddress". The request is basically declined or invalid, as no one confirmed it, which could be due to fraudulent / invalid email etc.
In this case, the system can and should remove all traces of the attempted change, especially since email Address is PII. All that stays is an anonymous sendout statistic. +You have not created a permanent (billable) duplicate Contact.
If a confirmation was given, SFSC & All Subscribers are updated, the email address is confirmed to be valid, you can store a permission, and you also have not created a permanent (billable) duplicate Contact as contact deletion removes the dummy key.
All the while it is a good idea to log what the different systems do.
Make sure you include "status", "source" & "timestamp" fields on the relevant objects so you always know WHAT was changed by WHOM and WHEN. Track statuses like "requested", "confirmed" at the different points so you can monitor what's going on and also pick up processes where they got stuck if something goes wrong.