Just a couple shots in the dark here (I'm pretty uninformed about MS-Windows systems)...

Would you be able to install a "unix-tools-for-windows" package that would be suitable to the setup on that machine? (Might have to compile from sources...) That would include a Windows version of the unix "find" command, which might work better than perl's File::Find module. (Or it might not work at all, given the file quantities and path lengths you're talking about.) It's worth a try, I think, esp. since it's really easy to use "find" from within a perl script:

my $basepath = "C:/where/to/start";

open ( FIND, "-|", "find $basepath -print0 ..." ) or die "can't start 
+find: $!";
$/ = chr(0);

while (<FIND>) {
    chomp;
    #  $_ is a path name that can be used with stat, etc
}
[download]

(update: I originally had the mode string wrong in the open() statement -- fixed it to "-|".)

If you're not familiar with the unix "find" command, it supports a vast range of option flags (to be added where I put "..." above). For instance, one thing that I found to be handy is to use "find" to get all the directories under a given top-level path, and then loop over those, using glob or readdir to do something with all the file names in each directory.