Just wanted to give another, final, update on those other servers just in case anyone finds this in the future and runs into similar issues.
This is the behavior I experienced on all three hosts (running on AWS-provided ami-0cd601a22ac9e6d79) -
Windows initially gives an error when trying to apply KB5034439 ("Download error - 0x80070643"). In my case the recovery partition has the appropriate amount of space on all of these hosts but KB5034439 still fails. After the initial failure of KB5034439 Windows does not try to install that patch again and it is removed from the list of updates by Windows itself, but the other updates will continue to fail.
On the first host I experienced this issue on I restarted the host after the updates were done installing and in pending restart and while KB5034439 was still showing as failed. At this point the other updates failed - they don't show as failed on the Windows Update UI, but they are rolled back on system restart. Subsequent attempts at installing the failed updates lead to the cycle repeating itself (although at this point there's no further mention of KB5034439). This was only resolved after the applying all of the fixes provided in this thread by Maxstar.
On the other two hosts that I had the issue on, instead of restarting once the non-failed updates were in pending restart status, I left the hosts up and did not preform a restart and instead I scheduled it for a later time. When I booted these hosts up afterwards Windows showed no issues in the Updates center, and checking for new updates never brought KB5034439 back up. So, seems that Microsoft is aware of these issues and has some procedure in place that attempts to correct the KB5034439 issues when they are unrelated to the amount of space left in the recovery partition (which is cited as the most common reason for this update failing). That's my theory at least.