The referenced paper is overly fussy, IMHO, because there are some preliminary questions to address. Chief among these is that the NSSDA implicitly models errors as approximately normally distributed and independent. Both of these assumptions are questionable, especially the second, and ought to be checked first. Their effects will be much stronger than the difference between, say, 10 and 100 links in your sample. The calculations are especially sensitive to the normality assumption.
As far as the sample size goes, as usual with statistical problems it depends on many things, of which one of the most prominent again is the assumption of independence of the errors. In practice, errors have strong spatial correlations. The nature of those correlations depends on what processing is performed. For example, the errors in scanned paper maps often will have periodic, anisotropic structure from the differential compression and expansion of the paper in preferred directions. Errors in orthophotos will be correlated with elevations and therefore inherit some of the spatial correlations of the topography itself, which obviously varies with terrain. A good assessment of spatial accuracy therefore requires an analysis of spatial correlation of errors and a distributional analysis of the residuals. For obvious reasons this is rarely (if ever) done. We just live with the fiction that the standard calculations are somewhat realistic and meaningful.
If we ignore all these (important) considerations, the question of sample size has a simple and well known answer: NSSDA estimates a standard deviation. Confidence intervals for standard deviations are constructed with chi-squared distributions. They can be computed even with Excel. Using these textbook formulas (no simulations required!) and starting with a desired level of confidence and desired target of accuracy in your estimate of the standard deviation, you can back-calculate the sample size needed. Because different applications depend in different ways on assumptions about positional accuracy, the needed "sample size and confidence" cannot be constant within all GIS work, but must be allowed to vary to reflect the intended use of the data.
