So, there is an update and solution: (see REAL solution comment xD)
The solution was to create a new GPO:
Computer config -> Policies -> Windows Settings -> Security Settings -> LocalPolicies -> Security Options -> "System cryptography: Use FIPS compliant algorithms for encryption, hashing, and signing" set to enabled.
roll that out to all Computers in the domain.
The only clue to that was on the remote client an Error in the System log Schannel (Event ID 38674) stating "An unknown connection request was received from a remote client application, but none of the cipher suites supported by the client application are supported by the server. The TLS connection request has failed."
Not even Wireshark was a clue, since the encryption negotioation is not very obvious.
This has to be an combination of a Windows update changing the RDP encrytion handling in Win11 and Server 2019 and some hardening in the past in the Windows domain.
If you stumble upon this: give the FIPS GPO a try and dont forget to reboot the affecting machines :)
If you want to verivy before rolling out a GPO, use the local Security Policy on the affecteed machines, there is the option too.