The current document discloses methods and systems for extending an internal network within a first cloud-computing facility to a second cloud-computing facility and deploying a virtual machine or virtual application previously running on a first cloud-computing facility within the context of the extended internal network in the second cloud-computing facility. The currently disclosed methods and systems which provide internal-network extension and redeployment of virtual machines and virtual applications, referred to as “stretch deploy,” allow a virtual machine or virtual application formerly executing on a first cloud-computing facility to resume execution on a second cloud-computing facility, using the computational and storage facilities of the second cloud-computing facility but depending on network support from the first cloud-computing facility, without changing IP and local network addresses and the network connectivity, based on those addresses, between the virtual machines and virtual applications and other local and remote computational entities with which the virtual machines and virtual applications communicate.