Ok, after spending 3 weeks with Microsoft's technical support department we have solved the problem.
The problem is with Dual Scan trying to connect to Windows Update (online) and failing. When it fails the system just stops trying and refuses to connect to WSUS.
The added problem is the server install media has a bug in it which prevents the Dual Scan from changing. It just ignores the policy and keeps the default update source Windows Update.
Here is what you have to do to fix it:
Run the following commands in Powershell on the offending server
$MUSM = New-Object -ComObject "Microsoft.Update.ServiceManager"
$MUSM.Services | select Name, IsDefaultAUService
You will get something back like this:
Windows Update Standalone Installer - False
Windows Server Update Service - False
Windows Update - True
If it says "Windows Update - True" Then that is your default source, no matter what your GPO says...
The first thing you have to do is make sure the following patches are installed on your server.
kb4103720 and kb4462928
You need them BOTH. They are both huge, they both take forever and a day to install and they both require a server reboot.
These KBs fix the dual scan issue so the server will respond to the GPO telling it which default source to use.
Now you need to configure Group Policy to tell the server to only use the WSUS server. Per Microsoft these are the required settings (I am dubious on some of them, but I haven't tested each one... I am just happy the thing is finally working)
Computer Configuration > Policies > Administrative Templates > System > Device Installation
Specify the search server for device driver source locations
Set to "Enabled"
Select search order: "Do not search Windows Update"
Specify the search server for device driver updates
Set to "Enabled"
Select Update Server: "Search Managed Server"
Computer Configuration > Policies > Administrative Templates > System > Internet Communication Management > Internet Communication Settings
Turn off access to all Windows Update features (In Microsoftspeak that means their online server, not 'make so it can't get updates')
Set to "Enabled"
Turn off access to the Store
Set to "Enabled"
Computer Configuration > Policies > Administrative Templates > Windows Components > Windows Update
Do not allow update deferral policies to cause scans against Windows Update
Set to "Enabled"
No auto-restart with logged on users for scheduled automatic updates installations
Set to "Enabled"
Specify intranet Microsoft update service location
Set to "Enabled"
Set the intranet update service for detecting updates: "http://[YOUR SERVER]:8530"
Set the intranet statistics server:"http://[YOUR SERVER]:8530"
Set the alternate download server: "http://[YOUR SERVER]:8530"
Uncheck the box Download files with no Url in the metadata if alternate download server is set
Move your servers into an OU with this GPO enabled. I created a separate OU in my Servers OU just for 2016 server and linked this GPO to it.
Run the above powershell commands again.
It should now say
Name IsDefaultAUService
------- --------------------------
Windows Server Update Service True
Windows Update False
If you get "Windows Server Update Service" True, then it should work!
I hope this helps someone else. This has certainly been a frustrating issue...
I accept donations in unmarked bills, gold bars and scotch.
Best Answer
In order to install the latest cumulative updates on a new installation of Windows Server 2016 you must first install the latest servicing stack update.
As of when this answer was posted, that meant installing KB4509091, but to find the most recent available servicing stack update you should always check security advisory ADV990001.
Once the servicing stack update was installed, KB4507459 no longer detected as not applicable and has now installed successfully.