I still haven't worked out the protocols for matching encoded locations -- hopefully it is possible. I fear you're right, I may not be able to get beyond a simple challenge-response type of comparison without disclosing some information.

Cool thing is, since I got interested in solving this problem, I've learned how R-Trees work! :)

http://en.wikipedia.org/wiki/Hilbert_R-tree