You can only remove a contact by changing the list memberships of the contact. To do this, you have to do a PUT to the contact URI. There is no way to remove a contact by only email address, though having the email address will let you do a query on the Contact Collection to get the URI you need.
"To do this, you have to do a PUT to the contact URI"
Please elaborate. I am trying to remove a contact as well. Is there some way to get the ID by reference of its email address?
Please see this post for how to retrieve a contact ID: http://developer.constantcontact.com/node/588#comment-944
You can also move a contact to the Do Not Mail list (which is a permanent removal rather than a temporary one). This can be done by sending a DELETE request to the contact URI. Please note that if you add a contact to the Do Not Mail list, Constant Contact requires that they request to be added back to your list prior to them being added back. Adding back any customers on your Do Not Mail list without their explicit request is against our Terms and Conditions.
For this reason, we typically recommend simply updating the contact to be on no lists. This will place them into a Removed state which you will not be billed for but can add them back from at any time.