Sorry for the very delayed reply. I sometimes miss some threads.
The number of samples required to obtain statistically significant results depends chiefly on two factors :
1) the size of the population tested. Obviously the sample size for Luxembourg can be smaller than for Germany, and Germany smaller than China.
2) the heterogeneity of the population tested. Some modern populations have grown very fast over the course of the last few centuries, while others have grown more steadily over the ages. I pointed out in a thread 3 years ago that in the early 19th century, Belgium was twice more populous than the Netherlands, while today the latter has a population 60% bigger than Belgium. Within Belgium, Wallonia use to be more populous than Flanders a few centuries ago. Flanders is now nearly twice as populous due to a much faster growth in the 20th century.
In 1350, France had a population of 20 million, only three times less than now. If we deduct all the people with foreign surnames in France (immigration of the last few centuries), we see that the French population has only grown 2.5 folds in the last 750 years, which is very little. In comparison, in 1350 Britain had a population of roughly 4 million (3m in England), Poland 2 million and Russia 8 million. These countries' populations have grown approximately 15 to 20 folds. Italy had 10 million and Spain 7 million - each experienced about a 6 fold increase.
So it's only natural that the genetic diversity should be higher in countries like France, Belgium, Italy and Spain than in northern or eastern Europe. In fact, the size of the historical population since the Middle Ages is fairly well reflected by the diversity of surnames. Italy, France and Belgium have the highest number of surnames per capita in Europe, while Scandinavia, the British Isles and most Slavic countries have among the lowest.
The second factor is the most important, yet also the most overlooked.
So what is the minimum sample size necessary to be relevant ? In northern and eastern Europe, where the medieval population density was much lower than in the former Roman Empire, I would say that 50 samples per million inhabitant (now) already gives a pretty good idea. This means 3000 samples for Britain, 2000 for Poland, or 250 for Denmark or Finland. Countries like Ireland clearly have more than enough Y-DNA samples to have a quite accurate picture. For countries like France, Belgium, Italy or Greece, 250 samples per million inhabitant are necessary, and they need to be selected carefully to cover every region, as there are often major disparities even in small adjacent regions (e.g. Cantabria vs Basque country, or Crete vs Peloponese, or Auvergne vs Rhône-Alpes). In other words, Belgium and Greece would need 2500 samples, France and Italy 15,000 samples.
Spain and Portugal are a bit different because a large part of the medieval (Muslim and Jewish) population was expelled in the 15th century, and the modern population therefore grew from a smaller portion of the medieval population, which explains why the surname diversity is also lower. I would place them in an intermediary category, along with Germany, and estimate that 100 samples per million inhabitant is representative enough (so 1000 samples for Portugal, 4000 for Spain, and 8000 for Germany).