I would hazard a guess that you have sharing rules on the account that are causing the contacts to be shared. However, you can definitely determine why by going to a "deleted" contact, and clicking on the Sharing button. From this page, click on the Expand List button, and choose the "Why?" Link next to a user that shouldn't have access. It will list all the reasons why a user has access. You can then fix the problem based on the information presented.
"Implicit Sharing"
The user has access to the contact because of a related record. You would need to remove or reassign all related child records.
"Manual Sharing"
The user was explicitly shared with this contact. Delete the share.
"Sharing Rule"
The user was granted access based on a sharing rule. You'll need to change the rule or change the contact so it no longer meets the rule.
"Administrator"
The user's profile has View All Data. Change the permission or the user's profile.
In summation, a soft delete isn't easy to implement easily. You would have better luck cloning the contact and deleting the original, but you'll lose the association with the child records.
The Expanded Sharing List
First, click on a contact, and you'll see the following buttons:
If you don't see this button, then either your sharing is set to Controlled By Parent, or your layout doesn't include the button. Try editing the layout (Edit Layout is in the upper-right corner right below the tabs). If it is present on the layout, and not visible, this means that sharing is set to Controlled By Parent, which basically means you need to see the account's sharing button instead. Check your sharing settings in Setup > Security Controls > Sharing Settings. The Organization Wide Defaults (OWD) for Contacts should be set to Private.
Once you have access to the Sharing button, click on it for the Contact in question. You'll see the following screen:
Click on the Expand List button, and you'll see the next screen:
Finally, locate the user that has access in the list (you may use the Rolodex to filter by name, or create views). Click on the "Why?" link, and then you'll see the reasons why the user can access the contact. It will look like this:
In this example, it shows that I have access to the record because I am an Administrator (Modify All Data), the Owner, and because of an Account Sharing Rule. Relationship will usually be Self or User's Manager, depending on that user's relationship.
So, in order to resolve this problem in this example contact, I would need to change the user's profile, change ownership of the record, and modify or remove the sharing rule, or even change the account the contact is associated to. Once you remove all reasons from this list, the contact will no longer be visible to the user.
