There is a nice mode that Samba supports which you can add to smb.conf
create mode=555
This way users can create and write files/directories without deleting (except I believe dirs can be deleted but only if there are no files inside).
It's too bad that Linux does not have built-in "write"/"delete" privileges and is something that even Windows 98 can trump.........