In the palaeoclimate world, palaeoecologists have used spatial training sets of say sea-surface temperture (SST) and related this to micro-organisms living at the locations where SST was measured. A popular model to predict SST from species assemblages (so you can count the same species from sediment core and thus predict SST back in time) is the Modern Analogue Technique (MAT). MAT is our name for $k$ nearest neighbours, but we are using it in a regression rather than the more commonly encountered classification setting.
In MAT ($k$-NN) we select the $k$ closest samples in terms of species composition to infer SST. Under standard (leave-one-out, $k$-fold, or bootstrapping) crossvalidation these models have very good performance stats and low model error compared to other modelling approaches. It has been shown that much of this improvement is due to the large degree of spatial autocorrelation in the training data. MAT is more able to use this information than some other techniques, hence the favourable RMSEP).
One solution suggested to this problem (of getting a realistic RMSEP or at least a better understanding of model error/uncertainty or even quality) is to use $h$-block crossvalidation, where samples with distance $h$ of the target sample are removed during crossvalidation. However, with MAT, these will necessarily be the observations that the model needs in order to predict that SST; by throwing out the samples within distance $h$ you are excluding sites with similar species composition and hence forcing the model to extrapolate. This is much less of a problem where the relationships between species and SST are "modelled" for example.
I'm wondering if there are other ways in which spatial autocorrelation can be handled within a $k$-NN framework. Are there better/alternative ways to tackle the problem of estimating an RMSEP for a $k$-NN model in a situation as I describe (strong spatial dependence in the training data). I have been thinking about using a dumb null model using spatial distance against which to compare the $k$-NN model, but that doesn't get at estimating an RMSEP that is not biased due to the spatial autocorrelation.