It often depends on what the actual dimensionality of the problem is. If it can be embedded in a lower dimensional space, as many problems are, then a well tune

It often depends on what the actual dimensionality of the problem is. If it can be embedded in a lower dimensional space, as many problems are, then a well tuned kD-Tree can still do a good job up to about 16 dimensions of used space, as you say. Cover trees also work well in this case, and are better at extracting just the salient dimensions than kD-Trees are, especially as the discrepancy between the subspace and data space grows. If the dimensionality gets larger then a better approach is to instead remove overhead and improve parallelism, for example by pushing the problem to the GPU or discretizing the measurement space down to 8-bits or even 1-bit per dimension. I know of products that do both, and solve O(N^2) problems 20x larger than a naïve approach could in the same time. POPCNT runs really fast on GPUs.