I did some further digging into it.
In the Windows Event log I found an entry that complained about missing files for "GameServices". Upon a bit of googling I found a tool from Microsoft that was supposed to fix this issue: GamingRepair.exe
So, turns out, that's probably just literally the binary they ship additionally to the game which gets stuck, probably some kind of timeout because it detects errors it can't fix.
Executed it myself and it gives you some output - error blabla.
Further googling, none of the fixes worked.
I ended up having to do an inplace upgrade of Windows that fixed the GameServices, since none of the resolutions I found online to fix it worked.
If you have this issue, you also can't use the Xbox App, it will error out.
Having the GameServices finally repaired, the Xbox App started to work properly again.
Afterwards the Steam Version of the game launched without any problems in like, 20 seconds tops.
No issues since, I have 8 hours in the game now.