An user discovered an strange "solution". The speedup can be improved if you install the Security Update for Windows Kernel-Mode Drivers (win32k.sys) if such an update is released at the current patchday.
For June 2016, the win32k.sys update is KB3161664.
Download the update (32Bit, 64Bit), stop the Windows Update service again, install the KB3161664 MSU and make a reboot. Now search again for new Windows Updates.