1. A non-transitory computer-readable storage medium having computer-executable instructions stored thereon that, when executed by a computer, cause the computer to: in conjunction with a migration of a virtual machine from a first host computer in a first network to a second host computer in a second network, notify a third host computer hosting one or more virtual machine instances to support a first mapping that maps a network address associated with the virtual machine to a network address associated with the first host computer and a second mapping that maps the network address associated with the virtual machine to a network address associated with the second host computer, wherein the third host computer receives network packets addressed to the network addresses associated with the first host computer and the second host computer, and substantially simultaneously sends a copy of the network packets addressed to the network addresses to both the first host computer and the second host computer; determine completion of the migration of the virtual machine from the first host computer to the second host computer; and in response to determining completion of the migration of the virtual machine, notify the third host computer to support the second mapping and discontinue support of the first mapping.