Hmm, well this may not help you, but the problem seems worse than you suggest. Even if you are able to deny "delete" support, the read+write (or even only write for that matter) will be able to overwrite existing files. This user could even overwrite the existing files with an empty version, thus, having the same effect as removing the file.
If it is imperative that the uploaded data remains safe from renegade users, you really need to make a separate account for each user, and only allow each user to write to their own location.
I don't, off the top of my head, see any other way around the problem.