Example methods are provided for a first host to maintain data-plane connectivity with a second host via a third host in a virtualized computing environment. The method may comprise identifying an intermediate host, being the third host, having data-plane connectivity with both the first host and the second host. The method may also comprise: in response to detecting, from a first virtualized computing instance supported by the first host, an egress packet that includes an inner header addressed to a second virtualized computing instance supported by the second host, generating an encapsulated packet by encapsulating the egress packet with an outer header that is addressed from the first host to the third host instead of the second host; and sending the encapsulated packet to the third host for subsequent forwarding to the second host.