First, you probably shouldn't assume that '.' and '..' are the first two directory entries returned from readdir(). AFAIK, this isn't guaranteed, so you should just check for them individually.

Second, are you mounting the filesystem over a network? For example, if you are using NFS make sure you test it with a hard mount or, if possible, test your code directly on the NFS server. NFS (and possibly other network filesystems) has to coordinate with the client on where in a directory it is reading from. I wouldn't be surprised if it's not exact on a huge directory since I've seen similar NFS bugs in the past.

One way to see if this is a filesystem issue, rather than in your perl code, is to use the 'find' command and count the lines in the output to see if you get inconsistent results.