Sounds like you have the permissions all out of whack. To start, anytime you apply the ‘deny’ permission it’s going to take precidense over all other permissions (share or NTFS). So be careful how you Deny.
If you have a shared folder and you want to give certain permissions to certain users/groups, apply the change or full control permission at the share level, then use NTFS to lock down the file. This prevents conflicts. Remember that when NTFS and share permissions are joined, the most restrictive permission wins.
If your wanting to allow users to delete files from within a folder you should give the users ‘modify’ permissions. This will allow them to create new files, write to existing files and delete files but restricts a user from changing effective permissions on the file. Only full control allows that.
There are a lot of good resources to be found on line that will explain in detail how permissions work and may help you better understand how to apply them in your environment. I’d suggest doing a bit of homework, then laying out a plan (flow chart) of what users/groups need what level of permissions before applying them.
When planning, don’t get overly complicated as that makes for administrative headaches. Keep your permission sets as simple as possible and you should be in good shape!