That's how our AP was designed. If a contact is removed from all lists, we change its status to REMOVED in the API, so that you don't get charged for a contact that's on no lists (and therefore, won't be mailed to until it gets added to a list).
You'd have to log into the account to do this. If you login to your account, search for a contact, and remove the lists from them, they will still be in ACTIVE status until you place them into removed status in the account. (There is a difference between the API and the functionality while logged in, in this respect. The API puts the contact into removed status when it's not on any lists; the UI makes you take an extra step to put them into removed status.)
Sorry for any confusion!
Partner API Support Engineer
View API documentation, code samples, get your API key.