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.
https://superuser.com/questions/922261/windows-8-1-stuck-on-checking-for-updates and https://superuser.com/questions/1103966/windows-update-doesnt-work-on-window-8-1 and https://superuser.com/questions/1189623/how-to-fix-windows-8-1-update-hanging and https://superuser.com/questions/1396051/windows-update-problems-after-fresh-windows-8-1-install and https://answers.microsoft.com/en-us/windows/forum/windows8_1-update/windows-8-update-searches-forever-solved/71976680-ccc5-4bd6-bfe5-f2f46ae7c734 – caw – 2019-05-02T06:51:09.347
1
Possible duplicate of Windows 8.1 stuck on "Checking for updates..."
– stiemannkj1 – 2019-05-02T16:03:26.993I had no luck with the existing answers, including the accepted answer. I did however persist and did eventually find a working solution which I have posted below. Perhaps this should become the accepted answer, as it seems to be more up to date. – Jackalope – 2020-01-06T19:43:33.913