In general, user should be capable to edit post to which media file is attached. It it’s true, user can edit this media file (attachment) property and delete it. ‘upload_files’ allows just to add new item to the media library.
If you turn ON the “Force custom post types to use their own capabilities” checkbox at the “Settings->User Role Editor->Additional Modules” tab, then WordPress will check ‘delete_attachments” capability instead of ‘delete_posts’. So you have to look if required capabilities from the “Attachments” group were granted to a role or user.
Some plugin can introduce a problem also. So all plugin temporal deactivation may help to isolate a reason.