Techniques are described for managing communications between multiple computing nodes, such as computing nodes that are part of a virtual computer network. In some situations, various types of modifications may be made to one or more computing nodes of an existing virtual computer network, and the described techniques include managing ongoing communications for those computing nodes so as to accommodate the modifications. Such modifications may include, for example, migrating or otherwise moving a particular computing node that is part of a virtual network to a new physical network location, or modifying other aspects of how the computing node participates in the virtual network (e.g., changing one or more virtual network addresses used by the computing node). In some situations, the computing nodes may include virtual machine nodes hosted on one or more physical computing machines or systems, such as by or on behalf of one or more users.