Cant update core or HAOS, cant reinstall either?

It means both machines can connect to GitHub and retrieve the file.
So it is not a network issue in its current position.

But it looks like the original failed update had /json in the end of the URL also.

They are not even “retrieving” the file, they are are saving a webpage, the same one you get when you click on it. The 404 error message relates to this:
http+docker://localhost/v1.41/images/ghcr.io/home-assistant/raspberrypi4-64-homeassistant:2023.2.5/json

I dont know what “http+docker” means, but its clearly a local file. So whatever needed to be downloaded isnt downloaded or doesnt end up in the right place.

Ugliest workaround ever: I make a backup of an addon or HA on the remote machine, download and restore it to a local HAOS VM, do the update, back it up again, then transfer the backup to the remote machine where I can restore the backup. Yeah. Not something Im gonna do on every update, but short of physically carrying the server back and forth, its all I have for now.

Yes to Double NAT, no to TPlink. I have a Netgear Nighthawk which appears to sometimes be a problem. I found a couple issues on github about the router.

10000000% the Deco. Exact thing has been happening to me since the day I installed my Deco Mesh System. It took much stress and hair loss figuring out why my HA would act as if it was updating but then reboot into the same version with no changes.

Turns out it could be a double NAT issue from what I researched. My workaround right now is to physically unplug the ethernet from the HA to the Deco and plug it directly from HA to router, reboot, do all my updates, and then switch back the cables when I’m done. To top it off it’s not in a convenient spot to reach lmao.

I have the same deco mesh at my own house (same provider too), same double NAT setup as my neighbour, with ISP router DMZ pointing to the deco, and no issues. I do not see anything different that could be relevant, and when I plug his HA server in to my home network, it updates fine.

I dont think “double nat” can even play a role here, as far as HA is concerned, there could well be 20 NAT routers between itself and github. People having issues with double NAT is usually for remote access, because they do not or can not configure both routers to forward the appropriate ports. For updates, this shouldnt matter, it should just download a file from the internet?

TL:DR as much as I hate deco for other reasons (WTF cant I even select a wifi channel!!), I just dont see how it could be to blame here.

You are correct. Double NAT should have no effect on this issue.
If it is not GitHub having issues, then the common causes is IPv6 issues, where the IPv6 is not configured correctly, but still active.
Do a ping to GitHub.com and see if it pings a IPv4 or IPv6 address.
Proxy servers might be an issue too, but this should then be the same when moving the device to the neighbor, unless the routers have been altered.
Firewalls can bein effect too, both blocking the connection due to some rule and/or dripping the connection due to some bug that occur when the load is high or the connection last too long.