WSUS 2016 - Clients not getting updates

Scenario:

• Windows 2016 Active Directory Domain Controller with default domain policy (GPO is applying to users fine)
• WSUS on separate Windows 2016 server

Problem:

Clients are not getting updates from the WSUS, On client side windowsupdate.log I see following errors

2018-08-25  11:12:06:878     868    28e8    Misc    ===========  Logging initialized (build: 7.6.7601.23806, tz: +0500)  ===========
2018-08-25  11:12:06:878     868    28e8    Misc      = Process: C:\Windows\system32\svchost.exe
2018-08-25  11:12:06:878     868    28e8    Misc      = Module: c:\windows\system32\wuaueng.dll
2018-08-25  11:12:06:878     868    28e8    Service *************
2018-08-25  11:12:06:878     868    28e8    Service ** START **  Service: Service startup
2018-08-25  11:12:06:878     868    28e8    Service *********
2018-08-25  11:12:06:893     868    28e8    Agent     * WU client version 7.6.7601.23806
2018-08-25  11:12:06:893     868    28e8    Agent     * Base directory: C:\Windows\SoftwareDistribution
2018-08-25  11:12:06:893     868    28e8    Agent     * Access type: No proxy
2018-08-25  11:12:06:893     868    28e8    Agent     * Network state: Connected
2018-08-25  11:12:07:673     868    28e8    DtaStor Default service for AU is {00000000-0000-0000-0000-000000000000}
2018-08-25  11:12:07:679     868    28e8    DtaStor Default service for AU is {9482F4B4-E343-43B6-B170-9A65BC822C77}
2018-08-25  11:12:07:706     868    28e8    Agent   WARNING: Failed to read the service id for re-registration 0x80070002
2018-08-25  11:12:07:706     868    28e8    Agent   WARNING: Missing service entry in the backup data store; cleaning up
2018-08-25  11:12:12:671     868    29c4    Report  CWERReporter::Init succeeded
2018-08-25  11:12:12:671     868    29c4    Agent   ***********  Agent: Initializing Windows Update Agent  ***********
2018-08-25  11:12:12:671     868    29c4    Agent     * Prerequisite roots succeeded.
2018-08-25  11:12:12:672     868    29c4    Agent   ***********  Agent: Initializing global settings cache  ***********
2018-08-25  11:12:12:672     868    29c4    Agent     * WSUS server: http://WSUS_WDS.MYDOMAIN:8530
2018-08-25  11:12:12:672     868    29c4    Agent     * WSUS status server: http://WSUS_WDS.MYDOMAIN:8530
2018-08-25  11:12:12:672     868    29c4    Agent     * Target group: (Unassigned Computers)
2018-08-25  11:12:12:672     868    29c4    Agent     * Windows Update access disabled: No
2018-08-25  11:12:12:672     868    29c4    DnldMgr Download manager restoring 0 downloads
2018-08-25  11:12:12:673     868    29c4    AU  ###########  AU: Initializing Automatic Updates  ###########
2018-08-25  11:12:12:673     868    29c4    AU    # WSUS server: http://WSUS_WDS.MYDOMAIN:8530
2018-08-25  11:12:12:673     868    29c4    AU    # Detection frequency: 2
2018-08-25  11:12:12:673     868    29c4    AU    # Approval type: Pre-install notify (Policy)
2018-08-25  11:12:12:673     868    29c4    AU    # Auto-install minor updates: No (User preference)
2018-08-25  11:12:12:673     868    29c4    AU    # Will interact with non-admins (Non-admins are elevated (Policy))
2018-08-25  11:12:12:910     868    28e8    Report  ***********  Report: Initializing static reporting data  ***********
2018-08-25  11:12:12:910     868    28e8    Report    * OS Version = 6.1.7601.1.0.196880
2018-08-25  11:12:12:910     868    28e8    Report    * OS Product Type = 0x00000007
2018-08-25  11:12:12:917     868    28e8    Report    * Computer Brand = VMware, Inc.
2018-08-25  11:12:12:917     868    28e8    Report    * Computer Model = VMware Virtual Platform
2018-08-25  11:12:12:919     868    28e8    Report    * Bios Revision = 6.00
2018-08-25  11:12:12:919     868    28e8    Report    * Bios Name = PhoenixBIOS 4.0 Release 6.0     
2018-08-25  11:12:12:919     868    28e8    Report    * Bios Release Date = 2016-04-05T00:00:00
2018-08-25  11:12:12:919     868    28e8    Report    * Locale ID = 1033
2018-08-25  11:12:13:686     868    29c4    AU  Successfully wrote event for AU health state:0
2018-08-25  11:12:13:686     868    29c4    AU  Initializing featured updates
2018-08-25  11:12:13:686     868    29c4    AU  Found 0 cached featured updates
2018-08-25  11:12:13:686     868    29c4    AU  Successfully wrote event for AU health state:0
2018-08-25  11:12:13:687     868    29c4    AU  Successfully wrote event for AU health state:0
2018-08-25  11:12:13:687     868    29c4    AU  AU finished delayed initialization
2018-08-25  11:12:13:687     868    29c4    AU  Triggering AU detection through DetectNow API
2018-08-25  11:12:13:688     868    29c4    AU  Triggering Online detection (interactive)
2018-08-25  11:12:13:688     868    28e8    AU  #############
2018-08-25  11:12:13:688     868    28e8    AU  ## START ##  AU: Search for updates
2018-08-25  11:12:13:688     868    28e8    AU  #########
2018-08-25  11:12:13:689     868    28e8    AU  <<## SUBMITTED ## AU: Search for updates [CallId = {E73FC668-DD83-4A67-B61F-900BA83F238B}]
2018-08-25  11:12:13:689     868    2bc0    Agent   *************
2018-08-25  11:12:13:689     868    2bc0    Agent   ** START **  Agent: Finding updates [CallerId = AutomaticUpdates]
2018-08-25  11:12:13:689     868    2bc0    Agent   *********
2018-08-25  11:12:13:689     868    2bc0    Agent     * Online = Yes; Ignore download priority = No
2018-08-25  11:12:13:689     868    2bc0    Agent     * Criteria = "IsInstalled=0 and DeploymentAction='Installation' or IsPresent=1 and DeploymentAction='Uninstallation' or IsInstalled=1 and DeploymentAction='Installation' and RebootRequired=1 or IsInstalled=0 and DeploymentAction='Uninstallation' and RebootRequired=1"
2018-08-25  11:12:13:689     868    2bc0    Agent     * ServiceID = {3DA21691-E39D-4DA6-8A4B-B43877BCB1B7} Managed
2018-08-25  11:12:13:689     868    2bc0    Agent     * Search Scope = {Machine}
2018-08-25  11:12:13:689     868    2bc0    Setup   Checking for agent SelfUpdate
2018-08-25  11:12:13:689     868    2bc0    Setup   Client version: Core: 7.6.7601.23806  Aux: 7.6.7601.23806
2018-08-25  11:12:13:695     868    2bc0    Misc    Validating signature for C:\Windows\SoftwareDistribution\SelfUpdate\wuident.cab with dwProvFlags 0x00000080:
2018-08-25  11:12:14:344     868    2bc0    Misc     Microsoft signed: NA
2018-08-25  11:12:14:346     868    2bc0    Misc    Validating signature for C:\Windows\SoftwareDistribution\SelfUpdate\TMPC956.tmp with dwProvFlags 0x00000080:
2018-08-25  11:12:14:382     868    2bc0    Misc     Microsoft signed: NA
2018-08-25  11:12:14:385     868    2bc0    Misc    Validating signature for C:\Windows\SoftwareDistribution\SelfUpdate\wsus3setup.cab with dwProvFlags 0x00000080:
2018-08-25  11:12:14:389     868    2bc0    Misc     Microsoft signed: NA
2018-08-25  11:12:14:392     868    2bc0    Misc    Validating signature for C:\Windows\SoftwareDistribution\SelfUpdate\wsus3setup.cab with dwProvFlags 0x00000080:
2018-08-25  11:12:14:396     868    2bc0    Misc     Microsoft signed: NA
2018-08-25  11:12:14:414     868    2bc0    Setup   Determining whether a new setup handler needs to be downloaded
2018-08-25  11:12:14:414     868    2bc0    Setup   SelfUpdate handler is not found.  It will be downloaded
2018-08-25  11:12:14:414     868    2bc0    Setup   Evaluating applicability of setup package "WUClient-SelfUpdate-ActiveX~31bf3856ad364e35~amd64~~7.6.7600.320"
2018-08-25  11:12:14:416     868    2bc0    Setup   Setup package "WUClient-SelfUpdate-ActiveX~31bf3856ad364e35~amd64~~7.6.7600.320" is not applicable
2018-08-25  11:12:14:416     868    2bc0    Setup   Evaluating applicability of setup package "WUClient-SelfUpdate-Aux-TopLevel~31bf3856ad364e35~amd64~~7.6.7600.320"
2018-08-25  11:12:14:431     868    2bc0    Setup   Setup package "WUClient-SelfUpdate-Aux-TopLevel~31bf3856ad364e35~amd64~~7.6.7600.320" is not applicable
2018-08-25  11:12:14:431     868    2bc0    Setup   Evaluating applicability of setup package "WUClient-SelfUpdate-Core-TopLevel~31bf3856ad364e35~amd64~~7.6.7600.320"
2018-08-25  11:12:14:454     868    2bc0    Setup   Setup package "WUClient-SelfUpdate-Core-TopLevel~31bf3856ad364e35~amd64~~7.6.7600.320" is not applicable
2018-08-25  11:12:14:454     868    2bc0    Setup   SelfUpdate check completed.  SelfUpdate is NOT required.
2018-08-25  11:12:14:537     868    2bc0    PT  +++++++++++  PT: Synchronizing server updates  +++++++++++
2018-08-25  11:12:14:537     868    2bc0    PT    + ServiceId = {3DA21691-E39D-4DA6-8A4B-B43877BCB1B7}, Server URL = http://WSUS_WDS.MYDOMAIN:8530/ClientWebService/client.asmx
2018-08-25  11:12:14:548     868    2bc0    PT  WARNING: Cached cookie has expired or new PID is available
2018-08-25  11:12:14:548     868    2bc0    PT  Initializing simple targeting cookie, clientId = 8d6e91d2-b2c4-45ab-8fa9-0efc7cac2969, target group = , DNS name = vc6.MYDOMAIN
2018-08-25  11:12:14:548     868    2bc0    PT    Server URL = http://WSUS_WDS.MYDOMAIN:8530/SimpleAuthWebService/SimpleAuth.asmx
2018-08-25  11:16:50:802     868    2bc0    PT  +++++++++++  PT: Synchronizing extended update info  +++++++++++
2018-08-25  11:16:50:802     868    2bc0    PT    + ServiceId = {3DA21691-E39D-4DA6-8A4B-B43877BCB1B7}, Server URL = http://WSUS_WDS.MYDOMAIN:8530/ClientWebService/client.asmx
2018-08-25  11:16:52:025     868    2bc0    Misc    WARNING: WinHttp: SendRequestToServerForFileInformation failed with 0x80190194
2018-08-25  11:16:52:025     868    2bc0    Misc    WARNING: WinHttp: ShouldFileBeDownloaded failed with 0x80190194
2018-08-25  11:16:52:037     868    2bc0    Agent   WARNING: Fail to download eula file http://wsus_wds.MYDOMAIN:8530/Content/23/14D19C27B28CC3990260D7191F6E0FF6C7483623.txt with error 0x80244019
2018-08-25  11:16:52:052     868    2bc0    Misc    WARNING: WinHttp: SendRequestToServerForFileInformation failed with 0x80190194
2018-08-25  11:16:52:052     868    2bc0    Misc    WARNING: WinHttp: ShouldFileBeDownloaded failed with 0x80190194
2018-08-25  11:16:52:056     868    2bc0    Agent   WARNING: Fail to download eula file http://wsus_wds.MYDOMAIN:8530/Content/23/14D19C27B28CC3990260D7191F6E0FF6C7483623.txt with error 0x80244019
2018-08-25  11:16:52:072     868    2bc0    Misc    WARNING: WinHttp: SendRequestToServerForFileInformation failed with 0x80190194
2018-08-25  11:16:52:072     868    2bc0    Misc    WARNING: WinHttp: ShouldFileBeDownloaded failed with 0x80190194
2018-08-25  11:16:52:082     868    2bc0    Agent   WARNING: Fail to download eula file http://wsus_wds.MYDOMAIN:8530/Content/23/14D19C27B28CC3990260D7191F6E0FF6C7483623.txt with error 0x80244019
2018-08-25  11:16:52:098     868    2bc0    Misc    WARNING: WinHttp: SendRequestToServerForFileInformation failed with 0x80190194
2018-08-25  11:16:52:098     868    2bc0    Misc    WARNING: WinHttp: ShouldFileBeDownloaded failed with 0x80190194
2018-08-25  11:16:52:111     868    2bc0    Agent   WARNING: Fail to download eula file http://wsus_wds.MYDOMAIN:8530/Content/23/14D19C27B28CC3990260D7191F6E0FF6C7483623.txt with error 0x80244019
2018-08-25  11:16:52:128     868    2bc0    Misc    WARNING: WinHttp: SendRequestToServerForFileInformation failed with 0x80190194
2018-08-25  11:16:52:128     868    2bc0    Misc    WARNING: WinHttp: ShouldFileBeDownloaded failed with 0x80190194
2018-08-25  11:16:52:139     868    2bc0    Agent   WARNING: Fail to download eula file http://wsus_wds.MYDOMAIN:8530/Content/D1/CDE5373D80E41F205260D2A7D8FB716A26BCA3D1.txt with error 0x80244019
2018-08-25  11:16:52:211     868    2bc0    Agent     * Found 0 updates and 76 categories in search; evaluated appl. rules of 942 out of 1694 deployed entities
2018-08-25  11:16:52:211     868    2bc0    Agent   *********
2018-08-25  11:16:52:211     868    2bc0    Agent   **  END  **  Agent: Finding updates [CallerId = AutomaticUpdates]
2018-08-25  11:16:52:211     868    2bc0    Agent   *************
2018-08-25  11:16:52:212     868    29cc    AU  >>##  RESUMED  ## AU: Search for updates [CallId = {E73FC668-DD83-4A67-B61F-900BA83F238B}]
2018-08-25  11:16:52:212     868    29cc    AU    # 0 updates detected
2018-08-25  11:16:52:213     868    29cc    AU  #########
2018-08-25  11:16:52:213     868    29cc    AU  ##  END  ##  AU: Search for updates [CallId = {E73FC668-DD83-4A67-B61F-900BA83F238B}]
2018-08-25  11:16:52:213     868    29cc    AU  #############
2018-08-25  11:16:52:213     868    29cc    AU  Successfully wrote event for AU health state:0
2018-08-25  11:16:52:213     868    29cc    AU  Featured notifications is disabled.
2018-08-25  11:16:52:213     868    29cc    AU  AU setting next detection timeout to 2018-08-25 08:06:28
2018-08-25  11:16:52:213     868    29cc    AU  Successfully wrote event for AU health state:0
2018-08-25  11:16:52:214     868    29cc    AU  Successfully wrote event for AU health state:0
2018-08-25  11:16:57:211     868    2bc0    Report  REPORT EVENT: {55A0D2DB-181F-48B2-A9C0-4BA58A45F18E}    2018-08-25 11:16:52:211+0500    1   147 101 {00000000-0000-0000-0000-000000000000}  0   0   AutomaticUpdates    Success Software Synchronization    Windows Update Client successfully detected 0 updates.
2018-08-25  11:16:57:211     868    2bc0    Report  REPORT EVENT: {BFEE6CC9-699D-45A5-BB20-6EAC4818656E}    2018-08-25 11:16:52:211+0500    1   156 101 {00000000-0000-0000-0000-000000000000}  0   0   AutomaticUpdates    Success Pre-Deployment Check    Reporting client status.
2018-08-25  11:17:59:222     868    2bc0    Report  Uploading 2 events using cached cookie, reporting URL = http://WSUS_WDS.MYDOMAIN:8530/ReportingWebService/ReportingWebService.asmx
2018-08-25  11:17:59:225     868    2bc0    Report  Reporter successfully uploaded 2 events.

.