Kolmogorov-Smirnov test - reliability Description
I want to use Kolmogorov-Smirnov test to check how given clusters of 1D points differs from normal distribution (original question here: How to test which data match model at best).
I am considering a following approach:
FOREACH cluster
  p = points FROM cluster
  n = SIZE(p)
  mu = AVG(p)
  sigma = SQRT(VARIANCE(p))
  tmp = GENERATE n RANDOM points FROM normal_distribution(mu, sigma)
  result = KS-TEST(SORT(p), SORT(tmp))
  IF result > threshold THEN ok OTHERWISE not ok

I took implementation of KS-TEST from here: http://root.cern.ch/root/html/src/TMath.cxx.html#RDBIQ
Number of points is usually hundreds or thousands.
Problem
I have observed that result strongly depends on randomly generated "tmp" points. Even when I randomly generated two sets of points from same distribution with same parameters, the resulting probability from KS-TEST floated between 0.0+something and 0.99+something. So it is difficult for me to choose a proper "threshold" value. The same cluster can be once considered as "close-to-normal-distribution" and once not.
Answer
Can you give me advice, what am I doing wrong, how can I get more reliable results?
 A: There are two standard versions of the Kolmogorov-Smirnov test:


*

*The one-sample KS, which tests if a sample of points $X_1, \ldots, X_n \in \mathbb{R}$ fits a specific continuous distribution function $F$.

*The two-sample KS, which tests whether it is reasonable to assume that two sets of samples $X_1, \ldots, X_n$ and $Y_1, \ldots, Y_m$ come from the same continuous distribution.


It seems that the code you are using only provides the two-sample version, but your problem is inherently a one-sample goodness-of-fit problem. It would be better to find an implementation of the one-sample test. This would eliminate the needless step of generating the variable 'tmp' and should increase the statistical power of the procedure.
Kolmogorov-Smirnov is often a bad choice since it completely lacks sensitivity at the tails of the distribution. I would recommend trying other tests such as the Anderson Darling test or the Berk-Jones tests.
As for the distribution of test results: this is expected. Under the null hypothesis (that the samples come from exactly the distribution you are testing against) the p-value computed for the Kolmogorov-Smirnov statistic is a Uniform[0,1] random variable.
In fact, this is always true for $p$-values under the null hypothesis when the statistic and the null distribution are continuous. For more information about this fact, see: "Why are p-values uniformly distributed under the null hypothesis?"
A: There are many tests for normality. This article contains the analysis of various factors that may affect results of the test. It was shown that among EDF tests Anderson-Darling test is more powerful than Kolmogorov-Smirnov test. However, other tests (e.g. Royston modification of Shapiro-Wilk test) have higher power in most cases.
A: This is the quote from International Encyclopedia of Statistical Science, p.1002

As indicated previously, the number of normality
  tests is large, too large even the majority of them to be mentioned
  here. Overall the best tests appear to be the moment tests,
  Shapiro–Wilk W, Anderson–Darling $A^2$... and the Jarque–Bera test.

See also Thode, HC (2002) Testing for normality. Marcel Dekker, New York
A: Absolute values of skewness and kurtosis could be both indexes of deviation from the normal distribution (be careful for the exact definition of kurtosis since most of statistical software subtract 3 by default). Then, having these numbers in two columns the most simple solution is to create a scatterplot and visually spot the outliers as the points that will lay far from the main body of the shape. 
If this method is not successful then as a more quantitative method I would not propose the formula |0 - Skewness| * |3 - Kurtosis| since there is no reason for a distribution to have both these values large or small, thus multiplication is not the appropriate procedure to detect deviations from normality. Instead of this and especially in case you will program it your self, I would propose as a simple solution the computation of the Euclidean distance from the skewness and kurtosis mean values $mean_{skew}$ and $mean_{kurt}$ defined as 
$$
d(cluster) = \sqrt{(mean_{skew} - \text{cluster skew})^2 + (mean_{kurt} - \text{cluster kurt})^2}
$$
and consider as outliers the greater 5% (or 10% it is up to you) of these distances.
Another option, that is used routinely in ANOVA methods is the computation of Mahalanobis distance for each cluster's pair of statistics (skewness, kurtosis) and consider as outliers all clusters with Mahalanobis distance greater than 13.82 which is the critical value of chi square distribution with 2 degrees of freedom at 0.001 significance level. If no cluster has Mahalanobis distance larger than 13.82 then you may simply consider as outliers the predefined percent of clusters with the larger absolute Mahalanobis distances.
Hope this will help you.
A: Do not random sample from your "truth" distribution
Instead, use the exact CDF here. Compare the empirical CDF to the modeled (exact, not sampled) CDF. The additional random sampling makes your results more unstable than necessary.
