I'm curious, did you test out the 'owner' idea by changing owners and re-running UserRecordAccess to see if they still have delete access?
My understanding of UserRecordAccess is that it does check profile/permission set permissions which is why it's different than just using the Sharing button on the record to determine access. That's at least what I found while writing a blog posting on how to build a custom sharing button (http://www.salesforcehacker.com/2013/09/build-your-own-custom-sharing-button.html) but I'll be curious to see if delete is somehow handled different due to record ownership.
Have you run SOQL to determine whether there is another reason why the user has delete? For instance:
SELECT Assignee.Name, PermissionSet.Id, PermissionSet.isOwnedByProfile, PermissionSet.Profile.Name, PermissionSet.Label
IN (SELECT ParentId
WHERE SObjectType = 'Account' AND
PermissionsDelete = true)
This would at least look across your user's profile and all permission sets to determine whether they have an object permission row that grants access.