An issue that I experienced in attempting to fix this was that the newly unallocated space from my recovery partition and the newly unallocated space from my main primary partition were not adjacent/contiguous in Disk Management view. When this is the case, windows cannot use ALL of the unallocated space on your drive, only the unallocated space blocks that are adjacent/contiguous to each other.
This meant that when I recreated the recovery partition (step 5 in https://support.microsoft.com/en-us/topic/kb5028997-instructions-to-manually-resize-your-partition-to-install-the-winre-update-400faa27-9343-461c-ada9-24c8229763bf ) then it ended up being the same size as before!
I had to use a 3rd party tool (AOMEI Partition Assistant Free) to merge both unallocated blocks back into my main primary partition and then afterwards re-shrink the primary partition by the size of my original recovery partition + 250MB in addition.
I then had a single unallocated block and could recreate the larger recovery partition.
Alas after all that, I actually still have the same issue trying to install this update (get error 0x80070643). I've even upped my recovery partition to 1GB (it was 529MB to start with) and still have the same issue so not sure that there's much else that I can do on this front!