Techniques are described for providing managed computer networks, such as for managed virtual computer networks overlaid on one or more other underlying computer networks. In some situations, the techniques include facilitating replication of a primary computing node that is actively participating in a managed computer network, such as by maintaining one or more other computing nodes in the managed computer network as replicas, and using such replica computing nodes in various manners. For example, a particular managed virtual computer network may span multiple broadcast domains of an underlying computer network, and a particular primary computing node and a corresponding remote replica computing node of the managed virtual computer network may be implemented in distinct broadcast domains of the underlying computer network, with the replica computing node being used to transparently replace the primary computing node in the virtual computer network if the primary computing node becomes unavailable.