Large-scale P2P applications (e.g., social networking, online gaming, video streaming) that host millions of users increasingly rely upon semi-structured super-P2P systems to provide efficient services in dynamic environments. Given the critical role of 'super peers' in such topologies, attackers target super peers due to the resultant high damage on P2P services. In this paper, we consider the prominent class of Outgoing Eclipse Attacks (OEA) where an attacker aims to block the communication by controlling all the outgoing connections of honest super peers. Our interest on OEA stems from the fact that our simulation studies reveal that OEAs can cause up to 90% of all service requests to fail. Our attack mitigation relies upon a novel (a) monitoring and (b) malicious peer eviction scheme based on a composite proactive and reactive mechanism. Our proactive mechanism enforces an upper bound on the number of connections an attacker can establish, whereas our reactive mechanism expels malicious peers from the overlay using a distributed consensus protocol. We show that our protection mechanism is highly effective and exhibits a low false-positive rate. Our extensive simulation study validates the analytical results over a large range of parameters with observed detection accuracies of 99% and throughput enhancements of up to 100% while entailing an overhead of less than 5%. © 2018 IEEE.