I connect daily from work to my home computer, which is behind a router with NAT. All I had to do to make it work was to enable port forwarding on the RDP port.
If you want to make it work with different computers, change the RDP port on the other machines (it's a registry key), and port forward them.