An illustrative “VM heartbeat monitoring network” of heartbeat monitor nodes monitors target VMs in a data storage management system. Accordingly, target VMs are distributed and re-distributed among illustrative worker monitor nodes according to preferences in an illustrative VM distribution logic. Worker heartbeat monitor nodes use an illustrative ping monitoring logic to transmit special-purpose heartbeat packets to respective target VMs and to track ping responses. If a target VM is ultimately confirmed failed by its worker monitor node, an illustrative master monitor node triggers an enhanced storage manager to initiate failover for the failed VM. The enhanced storage manager communicates with the heartbeat monitor nodes and also manages VM failovers and other storage management operations in the system. Special features for cloud-to-cloud failover scenarios enable a VM in a first region of a public cloud to fail over to a second region.