How to fix Windows 8.1 Update Hanging

Question

My Windows 8.1 laptop has not been updated for a long time. I am trying to run Windows Update > Check for updates but it keeps showing the Checking for updates... progress bar forever (more than 3 hours):

I tried all two approaches described in the YouTube video entitled "How To Fix Windows Stuck On Checking For Updates FIX 2017!" but none works. Namely:

1. Stop 2 services and delete all contents of the SoftwareDistribution folder.
2. Downloading from Microsoft and running the Windows Update Troubleshooter.

I also disabled the firewall, as suggested here:

https://answers.microsoft.com/en-us/windows/forum/windows_other-windows_install/fix-windows-updates-fail-to-install-in-windows-7-8/260f8566-8d0f-4535-817a-be01c6a9d0f7

But none worked for me. Is there any other trick that I can use to revive* my laptop's Windows 8.1 update?

*I'm saying revive because it used to work perfectly. I don't know when it stopped.

---

UPDATE:

@magicandre1981's 1st tip in his answer did the trick:

(the reason it says "Never" for "Updates were installed" is because during all my attempts to revive update, I have reset and clear the entire SoftwareDistribution folder)

Answer 1

Stop the Windows Update Service (via services.msc or in a cmd.exe which is started as admin via net stop wuauserv - this improves speed of installing the MSU update which you have to download), download and install this update by double click on the MSU:

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. Now Windows Update should work and show new updates in a few minutes. If not, stop Windows Update again and try the March 2016 Windows Update Client.