A remote access manager in a virtual computing services environment negotiates a time limited NAT routing rule to establish a connection between a remote device and virtual desktop resource providing user computing services. A series of NAT connection rules are revised in a dynamic manner such that a pool of ports is available to connect a plurality of remote users to local virtual compute resources over one or more public IP addresses. Once a connection is established, an entry is made in a firewall state table such that the firewall state table allows uninterrupted use of the established connection. After an entry has been made in the state table, or the routing rule has timed out, the port associated with the original NAT routing rule is removed and the same port can be re-used to establish another connection without disrupting active connections.