Last week we started having problems with our user's sessions to the remote desktop, investigating we found the issue was "supposedly" an error from Microsoft with an update, then we found some patches that supposedly fixed it, however we still have cases of users despite having the patch installed are able to connect to the remote desktop but if for some reason they disconnect, they can not reconnect, they simply receive an error message regarding the password.
If they wait a few minutes (more than 15 minutes) and try again, then possibly they can connect again. Another option is rebooting the workstations they are connected to and when they reconnect they do so without any problems.
We have followed up on the whole process and our DNS is fine, our Gateway is fine, so we have no idea where else to look.
By the way for our login validation process we use DUO Two Factor Authentication.