There may be a relevance issue with patch MS19-NOV: Cumulative Update for Windows Server 2016 - Windows Server 2016 - KB4525236 (x64). We have about 5% of our Windows 2016 servers failing to install this patch. Running it interactively on these servers you get the message “This update is not applicable to your computer”.
The only similarity of these server we can find so far is they are newly built servers.
Thanks,
Scott
What is the build version of your systems?
You can type “winver” to quickly get the build info.
KB4525236 represents build 14393.3326.
https://support.microsoft.com/en-us/help/4525236
If the servers are at a lower build version, then they do not have the Nov update and need it.
Perhaps check whether the November servicing stack update KB4520724 is installed on those. If it is not, then try installing that first and retry the cumulative.