1. A computer-implemented method comprising: configuring, by a computing system of an online service, and for a virtual computer network provided by the online service and having multiple computing nodes accessible via a substrate network on which the virtual computer network is overlaid, multiple devices in the substrate network that are provided by the online service, including storing virtual network addresses of the virtual computer network and causing each device to use the stored virtual network addresses to provide a specified type of functionality for communications sent between the multiple computing nodes of the virtual computer network; selecting, by the computing system, and to provide load balancing for the configured multiple devices in a manner that is based at least in part on specified configuration information for the virtual computer network, one of the configured multiple devices to use as an intermediate destination for a communication that is sent from one of the multiple computing nodes of the virtual computer network and that indicates one of the virtual network addresses as a final destination; modifying the communication to include encoded information specific to the substrate network, and forwarding the modified communication over the substrate network to the selected one configured device; after the forwarding of the modified communication over the substrate network, further modifying the communication to remove the included encoded information specific to the substrate network, and providing the further modified communication to the selected one configured device for further handling; and providing, by the selected one configured device acting as the intermediate destination and using the stored virtual network addresses of the virtual computer network, the specified type of functionality for the further modified communication before forwarding the further modified communication to the final destination.