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-...) 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?
Doing the PUT is the correct way to "revive" a deleted contact. The issue is that you need to do a GET first to locate the contact id. The default value of the GET status is for ACTIVE contacts which will not return deleted contacts. You will need to set the status to ALL or to DELETED in order to retrieve the information you need.
View API documentation, code samples, get your API key.