I found something interesting here:
Windows Modules Installer Error:126 - Microsoft Community
While the issue doesn't seem to be directly related to mine, there is an interesting response/solution there saying:
I was missing the following registry key:
HKLM\Software\Microsoft\Windows\CurrentVersion\Component Based Servicing\Version.
To fix it:
1. Navigate to C:\Windows\Servicing\Version and read the name of a subfolder. It will be named something like 6.1.7600.16385. That is your {TrustedInstaller ID}. Copy the name of that folder to the clipboard (and paste it in Notepad for safe keeping).
2. Find a subfolder in C:\Windows\WinSxS whose name starts with:
x86_microsoft-windows-servicingstack_31bf3856ad364e35_{TrustedInstaller ID} (32bit Windows)
amd64_microsoft-windows-servicingstack_31bf3856ad364e35_{TrustedInstaller ID} (64bit Windows)
Copy the name of that folder to the clipboard (and paste it in Notepad for safe keeping).
3. Create subkey "HKLM\Software\Microsoft\Windows\CurrentVersion\Component Based Servicing\Version". You will need to take ownership of "Component Based Servicing" then give yourself full access permissions before you can create the key.
4. In the new Version key, create an "expandable value" using the TrustedInstaller ID as its name and the complete path of the folder you identified in WinSxS as its value. Properly you should use %SystemRoot%\WinSxS\whatever instead of C:\Windows\WinSxS\whatever.
In my case, the (only) similar folder filename is:
x86_microsoft-windows-trustedinstaller_31bf3856ad364e35_6.1.7601.17514_none_93149d6fab68cf06
While I do have the registry entry, mine is:
Keyname: HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Component Based Servicing\Version\
Value name: 6.1.7601.23505
Type: REG_EXPAND_SZ
Type #: 00000002
Size: 222
Value: x86_microsoft-windows-servicingstack_31bf3856ad364e35_6.1.7601.23505_none_0bfc08bf3ea166ba
Your thoughts?