The trouble with symbolic links

The first two cases would also be an issue with hard links. You can't assume that a different path means a different file. And all three are possible with bind mounts, network filesystems, FUSE filesystems, or removable devices without involving symlinks in any way, so you need to handle those cases properly whether or not symlinks are available. For example the third case could be addressed by checking the device and inode numbers for each directory to prevent recursion, and also setting an absolute limit on the depth of the search.