The trouble with symbolic links

Not necessarily. Technically it would be enough to keep a reference counter and only allow permission changes when it is 0. The issue with that would be that it could go out of sync with the actual number of links pointing to the directory in certain situations but that is the same with the list.