If your positions are static (I'm not clear on that from your message), then you might want to check the technique of "slice searching".  It only requires one sort of the data for each dimension initially, then uses a simple, but clever look up to find neighbors within some epsilon of a chosen point.  Speeds appear to be about equal to k-d trees.  Programming is vastly simpler than k-d trees, however.