Update is not applicable to your computer- but it is

I encounter a rather weird issue with this error message, when trying to install an update: Update is not applicable to your computer, although it was.

Apparently this can also appear, because of the TrustedInstaller. To see if you are affected, view the CBS.log, you`ll see a lot of entries like:

, Info                  CBS    Failed to get Transaction State for package: Microsoft-Windows-DirectoryServices-DomainController-Tools-Package~31bf3856ad364e35~amd64~~6.1.7601.17514, update: DirectoryServices-DomainController-Tools [HRESULT = 0x80070bc9 - ERROR_FAIL_REBOOT_REQUIRED]
, Error                 CBS    Failed to get store state [HRESULT = , ,- ERROR_FAIL_REBOOT_REQUIRED]

So there is an issue here that the TrustedInstaller service changes the default service startup type of Manual (3) to Automatic (2), when it encounters an update that has to process a transaction after a restart.   When the value is set back to Manual before the restart the transaction that has to be applied after restart cannot be applied.  This transaction will be pended. It will block all other update installations that might come up.

You can check following key to see if you are affected, it should be 3: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\TrustedInstaller\Start

Resolution:

Start the TrustedInstaller service

Reboot the machine

You should be able now to install updates