Windows update doesn't work via double NAT for some computers

Here is an issue that tortured me for some loooong time and I still can't wrap my head around it: I've had huge issues updating Windows 11 on a brand new laptop of mine. It drove me crazy and I even reinstalled the OS because of it multiple times. Symptoms: The computer connects to the internet perfectly fine, browsers can navigate fine. Windows update fails silently (while it reports a success - way to go Microsoft!) The Windows Store cannot download/update apps (it gives an error code that sends you in a fruitless internet hunt) Edge cannot update itself (reporting something ironic and silly

Question by user2173353 on Super User, licensed CC BY-SA. We show a short excerpt and link to the original thread as credit.