V3 API Deleted Contact Not Found

Using V3 of the API I have come across the following problem. Trying to POST a new contact that is actually a delete contact returns a 409, as expected. I then try to do a PUT to update the existing contact (as suggested here as well https://community.constantcontact.com/t5/Developer-Support-ask-questions/Permanently-delete-contact-using-V3/m-p/334457) and the API returns a 404, the resource is not found.

How can I update the deleted contact via the API if both methods return errors?