I don’t have time to blog in detail today so I’ll point you to Ann Gibbon’s story, How Neanderthals lost their Y chromosome. You can find the link to the paper in there. The big issue here is that both mtDNA and Y chromosomes were replaced due to introgression from a population closer to modern humans than the Neandersovans, though basal to any modern humans alive today. This new group may actually be basal to the “basal human” group hypothesized by some scholars (there are suggestions of its existence in autosomal admixture into Neanderthals).
The probability of fixation of a newly introduced allele is the frequency of that allele, so how is it that these paleo-modern variants swept into Neanderthals? Perhaps on one locus, but two? One solution offered is naturals selection. This seems plausible, but the possibility of natural selection on Y and mtDNA lineages has always been a “wild card” that would make us rethink a lot of our phylogeography in general.
Finally, though it looks like the vast majority of modern ancestry outside of Africa is derived from a relatively recent (60,000 years ago) rapid expansion, it is clear that the picture at any given time is more complex than the signal we see today. It seems more and more likely that there was more a continuum between the African and Neandersovan lineages, and I strongly suspect that some of the paleo-modern lineages will at some point be detected in some modern groups once we have ancient DNA (the closer genetic distance and low fraction makes it hard for these segments to be identified in extant modern lineages using standard inference).