1. A computer-implemented method, comprising: providing, by one or more configured computing systems, a virtual computer network for a client in accordance with specified configuration information, the providing including overlaying the virtual computer network on one or more substrate networks and emulating functionality of one or more virtual router devices of the virtual computer network; forwarding multiple communications over the one or more substrate networks between multiple computing nodes of the virtual computer network that are specified to be inter-connected via the one or more virtual router devices, the forwarding including using information about locations of the multiple computing nodes in the one or more substrate networks; receiving, by the one or more configured computing systems, network routing information corresponding to one or more remote computing systems that are not part of the virtual computer network, wherein the receiving of the network routing information includes receiving one or more routing communications that are each directed to at least one of the virtual router devices and that include at least some of the received network routing information; and forwarding, by the one or more configured computing systems, one or more subsequent communications from the multiple computing nodes to the one or more remote computing systems based on the received network routing information.