Hi Neil, I solved this problem for windows 8.1 by installing KB3172614 which is a stand-alone update to the Windows Update application which was released in July 2016. Because it is a newer update than the one you mentioned in your original post, perhaps it was a easier fix to the problem of Windows update being stuck on checking for updates; I was able to resolve everything in about an hour.
Specifically I googled the update number and downloaded the appropriate version for x64 Windows 8.1 from the microsoft website. After downloading I saved the file instead of immediately installing. Then I turned off wireless so the computer was not connected to the internet. I then clicked on and installed the update in the download folder. Eventually the computer asked me to reboot and I did so. After the computer rebooted I turned the wireless antenna back on, making sure that the connection was manually set to 2.4GHz (not sure this made a difference). I then went to the Windows Update in the control panel and clicked on "Check for Updates". After about 5 minutes it was still "checking for updates" and I was about to give up, but suddenly it showed "updates found" the critical updates could be downloaded and installed in <30 minutes and everything seems stable now. I had previously run the Windows Update Troubleshooter as you suggested, but it just deleted my update history and did not seem to solve the problem at all.
Thanks for your suggestion to continue waiting. I never would have thought you would have to wait up to an hour for updates to be found!