Contacts are never deleted in our system, including in the UI. The "Delete" function of the UI simply marks them to not display. You can still export them and the history of their sends continues to exist.
Because the API needs to be able to access these Contacts to update, retrieve information and be associated to reporting information, we provide them all through a status filter of "Removed" as you saw. There is no way to permanently delete Contacts in the API as there is no way to delete them permanently in Constant Contact.
By deleting a list, or using the Bulk Activity to clear a list, you will automatically move your Contacts to a "Removed" state if they are not on any additional lists. If you are basically just automating clearing a list and adding new contacts to a list, I would highly recommend using our bulk API functions to do this. It is very simple to do the following pseudo-algorithm:
1. Create a Clear Contacts from List Activity: http://developer.constantcontact.com/docs/bulk_activities_api/bulk-activities-clear-contactlists.html
2. Create an Import Contacts Activity with up to 20,000 Contacts or 4MB of data: http://developer.constantcontact.com/docs/bulk_activities_api/bulk-activities-addcontact-multipart.html
3. Repeat step 2 if over 20,000k Contacts or 4MB of data until all Contacts are imported http://developer.constantcontact.com/docs/bulk_activities_api/bulk-activities-addcontact-multipart.html
All bulk activities are processes serially in the order they were created. So, you can actually simply create all these activities and poll until they all complete to ensure that the process worked correctly. Hope this helps!
... View more