HOW ON EARTH IS THIS STILL NOT SOLVED? MICROSOFT ARE YOU AWARE THAT ONLY PRE-BUILT PCS HAVE WIN-RE PARTITION THAT THIS UPDATE SEARCHES???? HOW ARE YOU THIS STUPID? EXACTLY THESE THINGS DRIVE PEOPLE TO APPLE !
Actually, I had the same problem with the update not installing correctly and I custom built my machine by ordering and installing all of the components & the OS. However, my machine was working just fine without the update so I wasn't sure why so many people were in a "panic" as if "It was a system-critical update that must be installed immediately but we can't install it!" I just wanted to see if I could get it installed by increasing the RP size and the way I had done it, was easy and carefree.
I didn't have to use any "command line commands" etc. Maybe more "advanced users" are better with those "terminal interface commands" but I had initially opened "Disk Management" and "shrunk" the system partition by ~250MB. This created "~250MB unallocated disk space" on C:. Well "Disk Management" would not allow "extending the Recovery Partition", it just offers "Help"....
So then I remember I had "Partition Wizard" installed, the basic version is still offered free. So I opened it and then I was able to "extend Recovery Partition" by moving the slider to "~250MB of unallocated space" and then I had a "Recovery Partition of ~780MB" because my RP was already ~530MB. I then clicked "apply", it completed the process in less than 5 seconds. I restarted my computer, re-ran the update, it installed without issue. No problems since. That was so easy and safe & no "command line commands" etc.