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.