Nice to see I'm not the only one. This has been happening for months, even before Win 10 free upgrades stopped. It's substantially worse in a business environment where you may wipe a machine and re-install several a day. I've tried the update rollup package after a fresh install and it says it's not applicable to my systems, so to me it's useless.
The only real solution I've found so far, is to stop Windows Update service, set it to Manual, download KB3050265, KB3065987, KB3102810, KB3135445, KB3138612, KB3161664, KB3020369, & KB3172605 and install them in that order, then check for updates. You can flip Windows Update service back to Automatic Delayed Start after that, and things seem to be okay. Sure is one hell of a pain in the ass though for each wiped machine several times a day.