Does KNN fail if the test data have no epsilon close nearest neighbors to the training data? If I have binary-classification data and a Euclidean metric, and I know the best number of nearest neighbors, then I draw circles on my training data based on my K-value which tell me which regions are from class A and B via voting.
How does KNN do prediction when I have new data points statistically outliers with respect to the training data and are located far away from the original training data? What if the test data have no nearest training data neighbors, and only has neighbors too far away to inference the membership?

At the risk of sounding obvious: you could test whether this is actually a problem in your dataset by plotting the NN-distance against the absolute value of the prediction residuals. If there's an upward trend there, you could annotate prediction confidence to your test point predictions based on the inverse of their distance to training points. I'm not aware of any preexisting packages that do this, I'm about to roll my own solution in R.
