I brought up this issue with the developers when EE 2 first came out and at the time there was no solution. I am now wondering if anyone has created any hacks, workarounds or add-ons that solve the issue?
The problem is the fact that EE insists on recreating all thumbnails every time you synchronize an upload destination. It does not recreate small or medium images (unless you tell it to) but there's no way to avoid the thumbnail recreation, which means that a batch addition of say, 100 images, to an already large gallery will take a very long time to process since all previous images will have their thumbnails recreated.