Ich musste auf einem Windows Server 2012 R2 die aktuellsten Updates installieren. Diese schlugen aber immer fehl. Der Windows Update Client zeigte mir viele offene Updates an:

D.h. der Server konnte bereits seit August / September 2018 (!!) die Updates nicht mehr korrekt installieren!
Ich versuchte zuerst, nur das aktuellste Update, und dann nur das älteste Update zu installieren. Beides schlug fehl.
Ein Blick in das Eventlog zeigte mir folgenden Fehler:

Die Fehlermeldung war bei jedem Update dieselbe.
Ich habe dann die aktuellsten Updates (KB4516067 und KB4516064) heruntergeladen, und per «wusa UPDATEFILE.msu» versucht zu installieren.
Auch das schlug fehl.
Nun folgte der Blick ins CBS.log (C:\Windows\Logs\CBS\CBS.log). Als ich von zuunterst des Logfiles nach oben nach «Error» suchte, fand ich folgende Fehler:
2019-09-18 09:17:29, Error CBS Failed to resolve package 'Package_1005_for_KB4054519~31bf3856ad364e35~amd64~~6.3.1.4' [HRESULT = 0x800f0831 - CBS_E_STORE_CORRUPTION]
[…]
2019-09-18 09:17:29, Error CBS Failed to process single phase execution. [HRESULT = 0x800f0831 - CBS_E_STORE_CORRUPTION]
[…]
2019-09-18 09:17:29, Info CBS Not able to query DisableWerReporting flag. Assuming not set… [HRESULT = 0x80070002 - ERROR_FILE_NOT_FOUND]
[…]
2019-09-18 09:17:29, Info CBS Not able to add %windir%\winsxs\pending.xml to WER report. [HRESULT = 0x80070002 - ERROR_FILE_NOT_FOUND]
2019-09-18 09:17:29, Info CBS Not able to add %windir%\winsxs\pending.xml.bad to WER report. [HRESULT = 0x80070002 - ERROR_FILE_NOT_FOUND]
[…]
2019-09-18 09:17:29, Info CBS SQM: execute time performance datapoint is invalid. [HRESULT = 0x80070490 - ERROR_NOT_FOUND]
2019-09-18 09:17:29, Info CBS SQM: Failed to initialize Win SAT assessment. [HRESULT = 0x80040154 - Unknown Error]
2019-09-18 09:17:29, Info CBS SQM: average disk throughput datapoint is invalid [HRESULT = 0x80040154 - Unknown Error]
Relevant ist in diesem Fall die oberste Zeile:
2019-09-18 09:17:29, Error CBS Failed to resolve package 'Package_1005_for_KB4054519~31bf3856ad364e35~amd64~~6.3.1.4' [HRESULT = 0x800f0831 - CBS_E_STORE_CORRUPTION]
Hier wird gemeldet, dass das Package «1005» des Updates «KB4054519» einen Fehler aufweist.
In «C:\Windows\servicing\Packages» kann nach der KB-Nummer (in diesem Fall «KB4054519» gesucht werden. In meinem Fall wurden 414 Elemente gefunden – nicht aber das Package «1005» (Suchbegriff «Package_1005_for_KB4054519»).

Das Problem kann behoben werden, indem das fehlerhafte KB (in meinem Fall KB4054519) heruntergeladen, entpackt und dann per dism in Windows eingepflegt wird:
Download: https://www.catalog.update.microsoft.com
Expand:
expand C:\Install\MSU\AMD64-all-windows8.1-kb4054519-x64_ad78da956d88ae3cd98982c11730240668c0e93f.msu /f:* C:\Install\MSU\KB4054519

DISM:
Dism /online /Add-package:C:\Install\MSU\KB4054519\Windows8.1-KB4054519-x64.cab

Danach konnten die aktuellsten Updates erfolgreich installiert werden.