Cannot install any updates on clean Windows 8.1

Stop the Windows Update Service (via services.msc or in a cmd.exe which is started as admin via net stop wuauserv), download and install this update:

Installing and searching for updates is slow and high CPU usage occurs in Windows 8.1

Do a reboot and check again for new updates.

I had this exact same problem.

You need the new version of windows update. The problem is, the patch notes for the updates you need don't actually tell you that they update windows update.

You need KB3173424 first, then install KB3172614. You should disconnect your computer from the network and restart before installing these after downloading.

https://www.catalog.update.microsoft.com/Search.aspx?q=KB3173424

https://www.catalog.update.microsoft.com/Search.aspx?q=KB3172614

I don't actually know if disconnecting your computer from the network to prevent windows update launching in the backround is necessary, but it worked for me. Similarly, I don't know if the updates must be installed in that order, or even if you need both of them. I just know it finally made the update process work. Hurray.

This problem continues into 2019, and, to my experience, none of the above answers are effective in the present day. At great length, I have been able to correct this issue with my Dell 3135 after a factory image restoration and installing update KB4504418 followed by KB3172614 & then KB4512488. Lots of helpful clues to be found in this thread. I did stop the Windows Update service before applying these updates, & I did apply them using an Administrative Command terminal, entering:

start /wait "" "%SystemRoot%\system32\wusa.exe" "C:\full\path\to\Update.msu" /quiet /norestart

as described in this very expert advice. (For those less savvy, you must replace the above path, "C:\full\path\to\Update.msu", with the explicit full path to the update module.

It is worth mentioning that I was unable to enact any of these updates in Safe Mode as advised in an earlier solution.