Since you've redeployed and recreated the VM and are still running into this issue I suspect that it may be a network issue (although it may be a good idea to check the VM and service health just to be sure). I know you set your priority but as a quick test you could try creating the following NSG rule:
- Go to your VM’s NSG (for “MyVM”, you’d go to “MyVM-nsg”)
- Under “Settings”, click on “Inbound security rules”
- Click on “+ Add” to create a new rule
- Set “Service” to “RDP”
- Set “Priority” to 100
- Name your rule and Save
These are the steps I would try next. If that doesn't work, let us know so we can troubleshoot this further:
- Verify Network Security Group rules. Use IP flow verify to confirm if a rule in a Network Security Group is blocking traffic to or from a virtual machine. You can also review effective security group rules to ensure inbound "Allow" NSG rule exists and is prioritized for RDP port(default 3389). For more information, see Using Effective Security Rules to troubleshoot VM traffic flow.
- Reset your RDP connection. This troubleshooting step resets the RDP configuration when Remote Connections are disabled or Windows Firewall rules are blocking RDP, for example. Select your VM in the Azure portal. Scroll down the settings pane to the Support + Troubleshooting section near bottom of the list. Click the Reset password button. Set the Mode to Reset configuration only and then click the Update button.
- Review VM boot diagnostics. This troubleshooting step reviews the VM console logs to determine if the VM is reporting an issue. Not all VMs have boot diagnostics enabled, so this troubleshooting step may be optional. Specific troubleshooting steps are beyond the scope of this answer, but may indicate a wider problem that is affecting RDP connectivity. For more information on reviewing the console logs and VM screenshot, see Boot Diagnostics for VMs.
- Check the VM Resource Health. This troubleshooting step verifies there are no known issues with the Azure platform that may impact connectivity to the VM. Select your VM in the Azure portal. Scroll down the settings pane to the Support + Troubleshooting section near bottom of the list. Click the Resource health button. A healthy VM reports as being Available.
For more detailed instructions, look at the Remote Desktop Troubleshooting guide: