CASE 1:
"Error 1719: The Windows Installer service could not be accessed" error message when you try to add or remove a program

Symptoms
When you try to add or remove a program, you may receive the following error message:
Error 1719. The Windows Installer Service could not be accessed. You may be running in safe mode or Windows Installer may not be correctly installed.

Cause
This behavior may occur if the following conditions are true:

• The Windows Installer files that are on your hard disk are damaged or are missing. 
• You install or remove a program that uses the Windows Installer Microsoft Software Installation (MSI) package file (.msi). For example, this may occur when you try to install Microsoft Office on your computer. 

Resolution
Method 1: Re-register the Windows Installer
Method 2: Reinstall the Windows Installer

How to resolute? Visit the detailed article at Microsoft's Support.
Source: Microsoft Support

CASE 2:

Repairing the Windows Installer service on a 64-bit OS
A customer recently contacted me due to a problem they were experiencing while trying to install the .NET Framework 2.0 on the x64 version of Windows Server 2003.  I took a look at the verbose log file for this scenario and saw the following error:

Action start 9:16:59: CA_InstallAssembly.3643236F_FC70_11D3_A536_0090278A1BB8.
MSI (s) (B0:F8) [09:17:03:906]: Product: Microsoft .NET Framework 2.0 (x64) -- Error 1719.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.

Usually when I see error 1719, I recommend that the user try to repair the Windows Installer service.  However, in this case, that didn't seem to help, and I had to refer this customer to the Microsoft technical support team for further assistance.

Our technical support team looked at this scenario in more detail and found that there was an additional set of steps needed to repair the Windows Installer service on a 64-bit OS.

Here is a complete set of steps that should allow you to repair the Windows Installer service on a 64-bit OS:

Click on the Start menu, choose Run, type cmd and click OK
Run %windir%\system32\msiexec.exe /unregister
Run %windir%\syswow64\msiexec.exe /unregister
Run %windir%\system32\msiexec.exe /regserver
Run %windir%\syswow64\msiexec.exe /regserver
Restart the computer
After executing all of the above steps, you can try to re-run the failing setup and hopefully get better results.

Note that this workaround is documented in this knowledge base article, but the extra steps that are needed on 64-bit operating systems are somewhat buried in the middle of that article and can be easy to miss.

Source: Aaron Sebner's WebLog
Published Thursday, July 20, 2006 8:02 PM by astebner
You may also visit Aaron Sebner's WebLog to learn about the error in more detail.

CASE 3:
A user's query:

My Installation Fails on Windows2000 Server with this error: Error 1719, 'The Windows Installer Service could not be accessed'. I understand that there is some problem with the Windows Installer Registration??? Is there something I can do to prevent it?

Another user's answer:

Can you re-install the MSI engine using the steps below :

• From a command line, run the following command:
  "msiexec /unregister" (without the quotation marks)
  If unregister fails, see the procedure that follows this one.
• Delete the Msi.dll, Msiexec.exe, and Msihnd.dll files from the system directory. You must rename these files from the command prompt.
• Restart Windows.
• Run the Instmsi.exe program from the installation CD or that you downloaded from the Web to install and register the engine files again.

Source: Community at Macrovision

Sources are explictly mentioned after each Case Scenario. DevInstall is not responsible for your damage if these steps did not follow as expected or you could not solve the issue using these ideas.