Windows Update has been getting stuck checking for new updates for the past several months. The automatic update somehow manages to complete, at least sometimes, but running a check manually doesn’t complete within a couple of days. It should be more like minutes, shouldn’t it?
I’ve tried various fixes with varying success — it seems that eventually Windows Update gets stuck again.
The best fix seems to be installing the latest convenience rollup update. I installed the one for August 2016, which thankfully1 is available as a standalone download.
Some further troubleshooting information and suggested fixes on Super User:
The Microsoft Update Catalog website is required for some rollup updates. That requires MSIE 6 or later. ↩