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?

When it comes time to predict, you take your new point $x$, find the $K$ training points closest to $x$, and use those $K$ points to make your prediction. There will be $K$ training points within some finite distance of $x$, so your question about if no points are nearest does not concern a situation that is possible.
If the training points are far away from $x$, you do the same process.
