Anonymity can protect from political repression in Online Social Networks (OSNs) as well as from undesired profiling, e.g., by advertisement companies, in todays’ Internet. P2P-based anonymous publish-subscribe (pub-sub) is a highly-scalable approach to protect anonymity while enabling efficient many-to-many communication between services and users. However, churn and the resulting overlay degradation in P2P-based pub-sub systems require repairs and optimizations to maintain anonymity and efficiency. This paper analyzes attacks on such repair and optimization functions to disclose participants. For that, we apply a strong attacker model that combines large-scale traffic monitoring with malicious insiders. Furthermore, we propose and evaluate heuristic countermeasures. Our findings indicate that some attacks can be mitigated at reasonable costs. However, churn seems to remain a major threat to anonymity.