Just a status report, I have managed to sync (43) folder with about 900 pics.
And this is somewhat promising, as these survived greater than 43 sync cycles without propagating corruptions.
As Stokie_Stez's tech support session have pointed out, iTunes "hits a wall" when it comes to what it preceives as an unviewable photo that it can't get iPad to display properly.
So if you try to sync the entire library of 10,000 photo you are very likely to get random shuffling of the unexpanded previews inside each folder, because you are likely to have a number of these "unviewable" that is causing the problem.
To get around it, I manually sync each folder and check for corrupted/missing photo against Lightroom 4(PC),
before I sync the next folder and build up the iPod Cache.
I also thumb to all the photo to ensure that all pics are indeed viewable without displaying the incorrect picture.
(again it is pretty easy to spot, square photo with large white borders, preview photo showing different photo when expanded, or just the number of pic sync not equal to those on the PC)
Each time I see a problem I go to my PC and delete that particular pic and sync again (in iTunes) to remove the "problem" off the iPad, then export the pic back again (with Lightroom 4) into the same folder and sync.
(this essentially remove the pic from the iPod Cache and back again)
If you just uncheck the folder to remove and recheck it to add, it will just pull the same problem off the iPod Cache, as nothing is modified.
I did run into about 15 or so of these "unviewable" among my (43) folders, but each time remedied.
Whatever you do, don't delete the iPod Cache (after the initial reset).
I am led to believe that the problem lies within iTunes, because if you kill off iPod Cache and rebuild your library using the above methods, a random photo become "unviewable" and you have to start from scratch again.
I recommend making a new folder for syncing to your 3rd gen iPad, that way the iPod Cache it is separated from other group of Apple devices.
All in all, this is all very tedious, it isn't entirely clear why auto sync works for iPad 2 but not this new iPad.