There exist many methods to detect recombination or mosaic structure in a sample of DNA sequences. But how reliable are they? Four methods were investigated with respect to their power to detect recombination in simulated samples with different amounts of recombination and mutation. In addition, we investigated the impact of the shape of the underlying genealogy on their performances. We found that the methods detected far fewer recombinations than were theoretically possible and that methods based on the principle of incompatibility in general had more power than methods that did not make use of this principle explicitly. This seemed, in particular, to be the case for phylogenies generated under population expansion scenarios which result in long branches at the tips and small deep branches. In addition to the results obtained through simulations, a series of new theoretical results on recombination is presented.