Windows Installer always fails with error 1601 or 1603 when run from a service

We have an application that gets installed at a customer's location. This application consists of a self-hosted WCF server running as a Windows service, as well as a client application that isn't related to this problem.

We publish updates to our customers by having the service download our WiX-generated .msi file in the background, then it is installed when the customer chooses to install it. The installation procedure is as follows:

1. The server copies a bootstrapper application to a temporary path and runs it, passing it the path to the MSI file to install
2. The bootstrapper uses the upgrade code in the MSI file to uninstall the previous version, then install the new version. It invokes the installer using various P/Invoke calls related to MSI's, like MsiInstallProduct.
3. The bootstrapper restarts the service

The issue is that at almost call customer sites, this automated process fails, though as with everything, it works in both testing and production at our location. Sometimes it fails during uninstallation, but normally it's during installation. Error codes 1601 (InstallServiceFailure) and 1603 (InstallFailure) are as common as they are entirely unhelpful in determining what went wrong.

We have a backup procedure whereby the user can manually invoke the installer by running the bootstrapper from within Windows (Run As Administrator is required, of course). This process works without fail, and it uses exactly the same installation logic as the automated process that fails.

All services are running as accounts with, at minimum, administrative privileges on the server box.

Where can I start in either trying to find more information about what is causing the error(s) or, even better, prevent them in the first place?

EDIT Here's one example of a failed install's verbose log file:

=== Verbose logging started: 3/29/2013  8:23:30  Build type: SHIP UNICODE 5.00.7600.00  Calling process: <<PATH TO MSI>> ===
MSI (c) (00:7C) [08:23:30:194]: Resetting cached policy values
MSI (c) (00:7C) [08:23:30:262]: Machine policy value 'Debug' is 0
MSI (c) (00:7C) [08:23:30:418]: ******* RunEngine:
           ******* Product: <<PATH TO MSI>>
           ******* Action: 
           ******* CommandLine: **********
MSI (c) (00:7C) [08:23:30:491]: Client-side and UI is none or basic: Running entire install on the server.
MSI (c) (00:7C) [08:23:30:520]: Grabbed execution mutex.
MSI (c) (00:7C) [08:23:30:562]: Failed to connect to server. Error: 0x800703FA

MSI (c) (00:7C) [08:23:30:605]: Failed to connect to server.
MSI (c) (00:7C) [08:23:30:637]: MainEngineThread is returning 1601
=== Verbose logging stopped: 3/29/2013  8:23:30 ===

This is too broad of a question to answer but here's what I've designed for other customers:

1) The elevated service downloads the MSI to a local directory and "advertises" (blesses) the MSI using the command msiexec /jm foo.msi

2) The non-elevated client side component then installs the MSI using the command msiexec /I foo.msi

The MSI must be properly designed and UAC compliant. The transition from Install UI to Install Execute will happen without a UAC prompt. Only properly scheduled ( deferred without impersonation ) custom actions will run elevated.

Once all the kinds were ironed out, the customer was very happy with their autoupdate pattern.