We have had the issue as well. I believe the problem is due to the fact that the RDS connection is trying to connect over UDP and is not trying to connect over TCP if the UDP fails.
If you add the following registry setting the Remote Desktop Connection will work.
Have to set this value to 1 in the registry for Windows 11 client to work outside the network
Computer\HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows NT\Terminal Services\Client
KEY VALUE - fClientDisableUDP SET TO 1
I am on the early adopter program with Microsoft and raised this exact issue with Microsoft when the beta came out for Windows 11 and they did not fix the issue.