Bingo! We tested BK trees and found them to break down on lots of data sets. The search speedup never overcame the additional cost of building the trees (although these were one-off sets, a search heavy workload could definitely benefit from them).
Interesting tid-bit, one Mr. Sergey Brin published this in 1995
"Near Neighbor Search in Large Metric Spaces"
http://www.vldb.org/conf/1995/P574.PDF
So I'm curious, because I had been planning on using a VP tree for something I'm mulling over. I could see stormy waters though for large dimensions.
Seriously interested to hear any feedback from people who have tried it. Any recommendations for what to do instead?