I know you're just dealing mostly with symlinks but I found (and generally known) that shutil.rmtree() is REALLY slow.  I found that for a RHEL 6 repo, removing the tree took, like, 9 seconds using shutil.rmtree() as opposed to milliseconds using system('rm -rf <path>').  I know it's not as portable but a hell of a lot faster.  Plus, doubt we'll run the server on anything but Linux anytime soon and we can deal with it then.