1. A computer-implemented method comprising: receiving, by one or more programmed computing systems of a configurable network service that provides virtual computer networks to customers, configuration information from a first customer for a first virtual computer network having multiple computing nodes, the configuration information including a specified network topology for the first virtual computer network that includes two or more of the multiple computing nodes being part of a pool of alternative computing nodes for use as intermediate destinations of at least some communications for the first virtual computer network; and providing, by the one or more programmed computing systems, the first virtual computer network for the first customer in accordance with the received configuration information by overlaying the first virtual computer network on a distinct substrate network without physically implementing the specified network topology for the first virtual computer network, the providing of the first virtual computer network including: before forwarding a first communication over the substrate network from a source computing node of the first virtual computer network to a destination computing node of the virtual computer network, selecting, based at least in part on the specified network topology, one of the alternative computing nodes of the pool to use as an intermediate destination for the first communication; and forwarding the first communication over the substrate network from the source computing node to the selected one computing node of the pool, to enable that selected one computing node to manage further forwarding of the first communication to the destination computing node.