Our org settings for Account and Contact is Public Read/Write. We have a user with custom profile. That profile additionally has View All on Contact and Account (but Modify All is not selected).
When the user tries to delete a Contact owned by a different user, he gets Insufficient Access. Why is that so if Contact is Public Read/Write?
There are four access levels in salesforce regarding a record (in increasing order of permission): readable, editable, transferable, and deleteable. The highest level you can ordinarily assign by sharing is transfer, and even then only on some types.
Each successive level of permission generally implies all lower levels, as well. For example, if you can delete a record, you can also edit it. The inverse is not true. Just because you can edit a record doesn't mean you can delete it.
Even with public edit permissions, nobody can ordinarily delete records not owned by them or their subordinates. This requires delete level record permission, granted usually by Ownership sharing (you own it, you can delete it) and management sharing (you can do anything to a record that your subordinate can do to that record).
There's also a limited sharing model that allows creating sharing rules that grant full access (aka delete access), but this isn't normally available. You'd need the financial management edition of salesforce, such as what Merrill Lynch uses.
Profile permissions such as modify all data overrides sharing rules. A user with modify all data can automatically delete any record for the types of data they have modify all data permission for. View all data only implies global read access, not edit or delete access.
Check to make sure the user is higher than the owner in the role hierarchy, see Note from help docs here:
You can delete a contact if you are an administrator, the contact owner, or a user above the contact owner in the organization role hierarchy, and if you have the appropriate user permission. If you delete or remove an activity’s primary contact, another contact becomes the primary contact in its place. You can edit the activity to manually select another primary contact.
