Under Windows 2000 Pro I was receiving the following error when trying to install Office updates or some Microsoft updates:

The Windows Installer Service could not be accessed.
This can occur if you are running Windows in safe mode, or if the Windows Installer is not correctly installed. Contact your support personnel for assistance.

I go this fixed by:
1) Booting in safe mode

2) Executing the following command:
msiexec /regserver

3) Reboot in "normal" mode.