The issue can be resolved by allocating an additional 250 MB of storage space to the recovery partition. Details on how to do that can be found here.
However, at least on Windows 10, Microsoft has acknowledged that an automatic resolution for this issue will not be released and as such, the only way to fix this is manually.
So there is a solution and the headline should be "Microsoft admits it can't automatically fix..."