If the conflicting Mail Contact is removed/deleted from the Target Tenant, subsequent "Prepare" actions will not remediate the problem, it will result in the same error. This is because Discovery does not currently detect deletions.
To resolve this, do not delete the offending contact, rather update the offending SMTP address so the conflict no longer exists. Once the conflicting address is modified, the next Discovery process will detect this change. Once discovery is completed, the "Prepare" action can be run on the user again.