Thank you for reaching out to Constant Contact's API Support.
You didn't specify which version of the API you are using; however in both versions we list our error code of 409 http.status.email_address.conflict. This error occurs when you attempt a POST on an email address that already exists in the account.
Based on your description you should be getting this error as you are trying to create a user with an email address that you already added to the account and deleted. Our system does not do a hard delete. You should be doing a GET on the email address first to see if the email address exists in the account first. If it does not exist then you can do a POST to create the contact. If it does exist then do a PUT to update the contact.
If you have any questions feel free to email us at email@example.com.