Si después de:
Solución 1: Volver a registrar Windows Installer
Solución 2: Actualizar Windows Installer a la última versión
Solución 3: Diagnosticar y solucionar problemas de instalación de programas automáticamente
Solución 4: Cambiar la configuración del servicio de Windows Installer
Solución 5: Cambiar las claves de registro (avanzada).
Sigues con las mismas deberías ir pensando en que el servicio se ha malogrado.
Yo mismo he reinstalado el sistema por la mala instalación de los .NET Frameworks desde Windows Update.
Prueba a "actualizar" el sistema sobre el sistema, renovarás los archivos a nivel sistema, pierdes los updates, y se respeta lo descargado e instalado. (Se mete el DVD con Windows en modo ON y se escoge ACTUALIZACIÓN).
Un saludo.