Modern botnets are progressively migrating to P2P network to resist against take-down attempts. In addition, new botnets use randomization in their behavior to evade detection. In this paper, we propose a new method for detecting stealthy P2P bots. We formulate the problem as a re-identification problem. This opens the possibility of powerful instantiations of detection algorithms to address the botnet detection problem. We also use a nontrivial feature selection technique to discover the best feature pairs for conducting comparison between two flows. We use real-world botnet data to evaluate the performance of Monsieur Poirot and compare it with existing flow-based algorithms. Monsieur Poirot is robust towards injection of noise in the communication patterns. The experimental results show that Monsieur Poirot is able to identify P2P bots with an average TPR of 98.65% and an average FPR of 0.21%.