Situation: The client has WSUS. The WSUS synchonization works fine.
The Last Status Report shows Installed is 100%.
However, the workstations don’t install the update and shows “Your device is at risk because it’s out of date and missing important security and quality fixes”
Cases 1:
I uninstalled this update (KB4058043) and did a manual cumulative update (KB4073290) which fixed the issue for me. Since then the error is gone from the Windows update.
Case 2: Install the latest cumulative update manually.
Case 3: Uninstall the KB4058043 Update.
Case 4: Make sure you have correct DNS settings.
Case 5: Have you been maintaining the wsus server in regard to using the server cleanup wizard? We were having issues at one time, and that fixed our issues.