That is very odd. Hard to answer w/o looking at the code or using strace. On some filesystems, the directory entry is a linked list of names with pointers to inodes. Maybe rsync optimizes in such a way as to require traversing the list the least amount of times? I'm just thinking out loud here...