Install the following Win8.1 update - KB3172614
Microsoft Update Catalog

this update rollup contains Windows Update Client v7.9.9600.18340 from KB3163023 that should resolve the long "checking for updates" problem

Thanks to erpster4 for their Microsoft Update Catalog suggestion. It took a long time but eventually found my updates and continues to check correctly.