This is the error that I get when I uninstall Office 2007 using the chrome tool. As you can see it's complaining about MSVCR80.DLL being missing. And it is after uninstalling Office 2007. I have tested it in multiple virtual machines and I get the same result every time. The solution to the problem was simple: I copied MSVCR80.DLL over from another unofficially updated Windows 2000 machine and placed it into system32. Now no error.
I just thought I'd post this little update. I can probably go ahead and remove Office 2007 with confidence now, and solve a lot of the other mentioned issues.