I have tested on a Windows Server 2003 Standard server successfully.
As long as the user is a member of the group the deny should take precedence.
The only thing I can suggest is make sure the user in question is not the one who created the folder, if so they are classified as the owner and can then delete.