As Parallels have been no help with this issue now for the 5 months that they have known about it, I have done by own debugging and discovered that the cause of this problem is the expiry of the Globalsign Root Certificate in Windows 2000 on January 28, 2014. This took me all of 5 minutes with my friend Google, so obviously Parallels developers do not care or they surely should have been able to resolve this issue months ago themselves.
To fix the issue, assuming you still have a non-corrupted Windows 2000 VM available (luckily I had a snapshot as the PT installation would corrupt the file system when it failed or attempted to roll itself back), make sure that Parallels Tools does not start installing, then simply follow the instructions at:
https://support.globalsign.com/customer/portal/articles/1434478
After which, I deleted the expired Globalsign Root certificate and forced a manual install of Parallels Tools which finished successfully! This is being posted from my Windows 2000 VM, no thanks to Parallels IP Holdings.
Last edited: Nov 30, 2015