How do you copy huge (millions) directory trees in Windows?

I have never seen robocopy fail like this, but if it is failing because of size/pre-indexing, then why not write your own script to do the copying? I would write the thing in PERL and just do the copy on a per-file basis and recursively go through it. You could add in checks in to see if the file already exists with the same time stamp, etc.

You could also check out RichCopy which is multi-threaded.

As some other answers have said, I've never seen RoboCopy fail like this - AFAIK, it doesn't do any indexing up front, it just starts with the first directory and gets on with the job.

Do you have the latest version of RoboCopy? There are some old copies floating around that date back to old NT days that can have problems with larger copies.

FWIW, here's the version header from my installation for comparison:

-------------------------------------------------------------------------------
   ROBOCOPY     ::     Robust File Copy for Windows     ::     Version XP010
-------------------------------------------------------------------------------

Not sure what else is on your partition, but you could use a Linux live CD (like GPartEd) and just copy the entire partition en-masse to the new drive. As a bonus, if you wanted to change the partition size while doing it, GPartEd will do that for you as well. Then delete whatever you didn't want to copy over. :)