Remote Desktop can't find the computer/Does not belong to the specified network.

Seems I have a similar issue to Remote Desktop can't find the compture (devolutions.net)

1. I am trying to access my desktop computer remotely (i.e. outside the home network that that machine is on).
2. I have verified the computer name is in fact correct, there's an open firewall rule for RDP, and RDP is enabled on that machine.
3. I am able to connect to that same computer when WITHIN that local area network through RDM.
4. I have setup a duplicate entry in RDM to the working local one, just changed the IP address to the public IP of the machine.
5. I have enabled port forwarding on port 3389 in my router, and am forwarding to the correct computer name.

When I try to start the session, RDM clocks for maybe 2 seconds before presenting me with this error message:



When I connect to that machine from WITHIN the LAN, it's literally the same computer name so "verify computer name" doesn't help much here. I have poked the correct hole in the firewall and setup port forwarding for port 3389 already, so what's the deal here? What could I be missing?