1. A computer-implemented method comprising: instantiating, by one or more computing systems implementing a program execution service that has a plurality of server devices for use with customers of the program execution service, a first virtual network for a first customer of the program execution service; configuring, by the one or more computing systems and for a first server device of the plurality that hosts at least a first virtual machine, a communication manager of the program execution service on the first server device to associate the first virtual machine with the first virtual network, the configuring including storing mapping information on the first server device for the first virtual network that includes information about a second virtual machines in the first virtual network, wherein the second virtual machine is hosted by a second server device of the plurality; receiving, by the communication manager of the first server device, an outgoing communication sent from the first virtual machine to a destination virtual machine that is the second virtual machine, wherein the outgoing communication has an indicated virtual network address for the destination virtual machine, and wherein the first server device has connectivity to a second network that is a physical network including the second server device; verifying, by the communication manager of the first server device, that the received outgoing communication is authorized based at least in part on the first virtual machine being allowed to communicate with the destination virtual machine; modifying, by the communication manager of the first server device and based at least in part on the stored mapping information, the outgoing communication by adding to the outgoing communication a destination network address for the second network that is associated with the second server device; and initiating, by the communication manager of the first server device and based at least in part on the verifying that the received outgoing communication is authorized, sending of the modified outgoing communication to the second server device via the second network based on the destination network address for the second network.