How to give users permission to create and rename a folder, but not to delete it?

view story

http://serverfault.com – so i'm trying to make a shared folder for other users, inside that folder i want a personal folder for every user. I have given full control to everyone on the network, so i can do anything i want, i tried to remove the "Delete" permission but than i couldn't create a folder with a new, which would mean all my folders are called "New Folder". Is there a way to fix this? Or will i have to trust that my users doesn't delete everything. (HowTos)