How to create a directory users can't delete (but can delete files in it)?
Solution 1:
In your scenario where the directory is /share/permanent/
mkdir -p /share/permanent
chmod 755 /share
chmod 777 /share/permanent
sudo chown -R root:root /share
This works because now deleting /share/permanent would be considered writing to share, which is only writable by root. /share/permanent/ can be written to by and read by anyone.
If you want to make it so that people can only delete file that they own you can set the +t flag with chmod.