I don't know about your specific components, but here's what I found out:
Two different kinds of Software Installation GPOs exist: Assign and Publish.
Publish is the easy one, the package is added to ARP, network installs. The package is a "managed installation", meaning that any user can install it - the InstallExecute sequence is run under the account set for the Installer service (usually LocalSystem).
Assign is the tricky one. During the GPO execution the package is Advertized. When the software is activated, the actual installation of the necessary feature(s) takes place. Advertizing is a bit tricky here: Rumor goes this installation is performed by the DC, not the target system. Look in the AdvtExecuteSequence in the final MSI, make sure it reads exactly like prescribed in the SDK. I've seen some MSMs that modify this table - eg. InstallShield MSM for MDAC 2.6sp2 tries to install MDAC on the DC.
How to go ahead:
I don't think that your install problem is related to the warning in the event log. Look on
http://www.eventid.netIf your package is published (not assigned), you may find missing HKCU entries, since the package was installed with another account.
If your package is assigned, better look into Advertizing first.
You can perform Advertizing as follows:
MsiExec /ju <NetworkImage>
If that results in the same problem, you may want to review your feature tree. When a program is started, it only installs a minimal set of features: just the feature itself, and parent feature, it's parent feature, etc.
Finally, a policy exists that creates a log for every install action available - including the activity when a program is started, but needs to install the advertized feature first.
Hope this gets you started.