Techniques are described for managing communications for a managed virtual computer network overlaid on a distinct substrate computer network, including for communications involving computing nodes of the managed virtual computer network connected to the substrate network and/or other external nodes of the managed virtual computer network that are not connected to the substrate network. The managed virtual computer network may have multiple associated virtual network addresses, and the managing of the communications may further include using one or more edge modules to direct all communication that have a destination virtual network address within a range or other group of multiple virtual network addresses assigned to one or more external nodes to be forwarded over the substrate network to an edge module associated with the one or more external nodes, including to route communications between different external nodes via the substrate network.