Fast high-dimensional K-nearest neighbors
For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\alpha)$ for some $\alpha &lt; 1$. 

On the other hand you can do better if you are ok with approximation. Locality sensitive hashing can be used to achieve subquadratic in $N$ running times while reporting points which are not much further than the nearest neighbors. 

For subsets of Euclidean space with doubling dimension $d$ (which captures the lower-dimensional manifold situation), Indyk and Naor show that there is an embedding into $O(d)$ dimensions (in fact a random projection in the style of the Johnson-Lindenstrauss lemma) which approximately preserves nearest neighbors. If $d$ is small enough you could first apply the embedding, then use a nearest neighbor data structure for low dimension.

You could also try the random projection trees (RP-trees) of Dasgupta and Freund. They are a natural variant of kd-trees in which the cut in each level is done in a random direction, rather than a coordinate direction. I don't think there are any known provable guarantee for how well RP-trees do on nearest neighbor problems, but the paper I have linked does prove that the trees adapt nicely to doubling dimension, so there is hope. The guarantee they give is that, if a point set inside a cell has doubling dimension $d$, then the descendants of the cell $O(d\log d)$ levels down the tree have diameter at most half that of the cell.