Hi Michael Born1
It seems that you've already gone through the basic troubleshooting steps. However, because the problem doesn't happen the same way for all devices or users, it's a bit tricky to figure out what's causing it precisely.
Considering this inconsistency, we recommend using Wireshark to capture network packets when you're making an RDP connection. This will give us a closer look at the network activity during these connection attempts.
Regards,
Karlie