Connectivity is enabled between a first and second isolated network using a virtual traffic hub that includes a decision master node responsible for determining a routing action for a packet received at the hub. At the hub, a determination is made that a particular domain name system (DNS) message being directed to a first resource in the first isolated network is to include an indication of a second resource in the second isolated network. The second resource is assigned a network address within a private address range of the second isolated network, which overlaps with a private address range being used in the first isolated network. The hub causes a transformed version of the network address to be included in the DNS message delivered to the first resource.