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.