Hey, Maree. It isn't so much about extended time and effort required to piece together good yDNA evidence as it is having multiple test-takers at high resolution levels of testing who also have well-researched family trees. So it's either luck (many related men just happened to take tests) or--the typically lengthy part--an organized plan to identify, seek out, and have tested specific men whose data can contribute information to a particular family line.
And, yep, with either of the uniparental DNA types--yDNA or mtDNA--it's always easier to prove a negative hypothesis than a positive one. That's one reason autosomal DNA was such a fantastic addition to the toolkit: genealogically it's of little use beyond 5th cousins--a shared 4g-grandparent--but it's great at close relationships and it can actually be predictive of the degree of cousinship. Plus it doesn't discriminate: everybody inherits it the same way.
Uniparental DNA, specifically because it escapes crossover during meiosis so recombination never takes place, can look many generations deeper. While yDNA can't be predictive about a relationship between two male cousins, it can still yield solid evidence that the two men share a common paternal ancestor within a handful of generations. And the information in the SNPs, the single nucleotide polymorphisms, can trace an ancestral chain from hundreds to many thousands of years ago. Mitochondrial DNA--which isn't part of the human genome at all and is a positively tiny molecule consisting of only 16,659 base pairs and 37 coding genes (compared to the Y-chromosome's 58 million base pairs with only twice as many genes)--is of least use in genealogy because there is so little room for non-harmful mutations to happen and the mutation rate is glacially slow. But mtDNA has the same non-recombinant trait and can look back thousands of years along the matrilineal line.
Because uniparental DNA can show an unbroken line of DNA inheritance over the course of thousands of years, it easily predates the times when surnames began to be adopted, regardless of the geographical region. You're absolutely correct: because of that, we can't be quick to rush to judgment about surname differences as displayed by yDNA testing. I mentioned Wales as one location that stayed with a patronymic naming tradition hundreds of years after surnames began to be adopted in England, as did, for example, Ireland and most Scandinavian countries.
In Joseph's case, I wasn't meaning to theorize but just offer a what-if sort of example. The most common surnames in Wales today are Jones, Williams, Davies, Evans, Thomas, Roberts, Lewis, and Hughes. In their patronymic convention, a person's given name would be linked by ap or ab (son of) or ferch (daughter of) to the father's baptismal name. So there could have been, in the same yDNA line, an Evan son of William or Evan ap William, then a Thomas ap Evan, a Dafydd (David) ap Thomas, and a Williams ap Davies when, boom, surnames began to be adopted. Some in the very same line may have chosen Davies or Davis, some Williams, and some Thomas.
It's much easier to construe an NPE over surnames when dealing with autosomal DNA because we're only looking back a handful of generations, at best. With yDNA we have to be much more careful because we might easily be looking at unbroken male lines that have no recent NPE, that in fact separated many hundreds of years ago from the same ancestor. This is a common problem for male adoptees who take yDNA tests: it can reveal a stockpile of important information, but it doesn't have the immediacy or predictive nature of autosomal results. A few yDNA matches to the Smith surname doesn't mean the birth father was named Smith. It's definitely a clue, but not yet evidence. IMO, the mantra should be to test everything the pocketbook will bear, but go into it understanding how to interpret and evaluate the results.
As for sources to learn more about yDNA, a place to start--especially if you prefer multimedia over mounds of text like I generate <cough> 
--might be a couple of YouTube channels. Family Tree DNA pioneered yDNA testing, so you can't really overlook them. The YouTube channel is here. They don't do regular webinar/instructional posts like they used to, but you can look through their videos and find several pertaining yDNA testing and interpretation of results.
Maurice Gleeson is a frequent lecturer on using yDNA in surname studies, and is kind enough to post a lot of those on YouTube. You can find his channel here.
If there is British Isles ancestry, another good channel is Genetic Genealogy Ireland. Dr. Gleeson contributes there, as have John Cleary, Brad Larkin, Debbie Kennett, and others.
There are, of course, some rather oddball postings on YouTube about yDNA--well, about everything--so I'd personally stay with those until you feel comfortable in identifying the, er...odd from the useful. Have fun!
