The problem/solution is listed here: https://support.microsoft.com/en-us/topic/kb5028997-instructions-to-manually-resize-your-partition-to-install-the-winre-update-400faa27-9343-461c-ada9-24c8229763bf
That is not a solution, that's a workaround. In the meantime (check bleepingcomputer.com and others) there are people with sizes way more than enough still getting this error.
On 1 pc with 547 MB space I tried this "solution" and got hanging on step 8, not able to enable reagentc anymore.
So I used a new install from usb, removed all partitions and installed again. Now this time, after installation and updates the update went fine.
Guess what... sizes of recovery partition... 547 MB.
So how come it's the same size and this time no errors?
Now on my own pc, same error on updating. My pc has a 600 MB rescue partition and right next to that on the right side, an unused unpartitioned space of over 400 MB so windows could have taken what it needed. But it didn't. I call that bad programming if that isn't even checked.
There are people around with 1 GB of recovery partition getting this error, which is way more than enough space.
Mainstream users don't have that knowledge and don't risk things. Microsoft should just fix this update.