I assume you are aware of the classic paper by Jon Bentley, "Multidimensional divide-and-conquer" [Commun. ACM 23(4):214-229 (1980)], in which he showed how to find the closest pair of points in $\mathbb{R}^3$ in the Euclidean metric in $O(n \log n)$ time. His algorithm works in arbitrary dimensions , with the constant dependent on in $d$. O(n \log^{d-1} n)$. I realize I am not answering your question about metric spaces, but it might be worth revisiting his algorithm to see how heavily it leans on the norm. Rabin's 1976 randomized algorithm achieves$O(n)$expected time. An updated detailed analysis is in the paper "A Reliable Randomized Algorithm for the Closest-Pair Problem" by Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen [Journal of Algorithms 25(1): 19-51 (1997)]. Again I am not addressing your focus on other metric spaces, but these efficient algorithms for Euclidean distance would be a place to start. 1 I assume you are aware of the classic paper by Jon Bentley, "Multidimensional divide-and-conquer" [Commun. ACM 23(4):214-229 (1980)], in which he showed how to find the closest pair of points in$\mathbb{R}^3$in the Euclidean metric in$O(n \log n)$time. His algorithm works in arbitrary dimensions, with the constant dependent on$d$. I realize I am not answering your question about metric spaces, but it might be worth revisiting his algorithm to see how heavily it leans on the norm. Rabin's 1976 randomized algorithm achieves$O(n)\$ expected time. An updated detailed analysis is in the paper "A Reliable Randomized Algorithm for the Closest-Pair Problem" by Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen [Journal of Algorithms 25(1): 19-51 (1997)]. Again I am not addressing your focus on other metric spaces, but these efficient algorithms for Euclidean distance would be a place to start.