Are there any packages in Python that allow one to do kdtree-like operations for longitude/latitudes on the surface of a sphere? (this would need to take into account the spherical distances properly, as well as the wraparound in longitude).
A binary search tree cannot handle the wraparound of the polar representation by design. You might need to transform the coordinates to a 3D cartesian space and then apply your favorite search algorithm, e.g., kD-Tree, Octree etc.
Alternatively, if you could limit the input range of coordinates to a small region on the surface, you could apply an appropriate map projection to this region, i.e., one that does not distort the shape of your area too much, and apply a standard binary search tree on these no-wrap-around cartesian map coordinates.