none of the above worked for us, but this blog post solved it:
http://www.joelleach.net/2024/12/30/windows-server-appx-installation-failures/
in short, the reg key
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Notifications
is bloated with thousands of entries, emptying it solves it !
RDSH servers with many users will have this key filled up over time