1. A non-transitory computer-readable medium having contents that, when executed, configure a computing system to manage communications by performing a method comprising: managing, by the configured computing system, a first communication that specifies a first virtual network address associated with a first computing node of a first virtual computer network, the managing of the first communication including identifying a distinct substrate network address for the first computing node that corresponds to a network location of the first computing node in a substrate network, the substrate network address being identified based at least in part on mapping information for the first virtual computer network that associates the first virtual network address with the substrate network address; after the managing of the first communication, determining, by the configured computing system, to initiate a change to the first computing node that results in a modification of the associated first virtual network address for the first computing node or of the substrate network address for the first computing node; updating, by the configured computing system, the mapping information to reflect the change to the first computing node; and managing, by the configured computing system, a second communication sent to the first computing node by using the updated mapping information to identify a current network location of the first computing node in the substrate network.