As of today, I run Mojave, Mavericks and Lion: Mavericks and Lion are on the internal drive while Mojave is on the external one. I used to have problems in Mavericks and Lion at different points in time. The solution below takes into account the fact you don't use proxies.
For Mavericks and Lion I used to have Spotlight disabled for a long time enabling it only for the macOS I'm working currently in. I don't have an explanation of why it hit Mavericks and Lion but not Mojave but I suspect it's due to the incorrect indexing of metadata across all of the bootable partitions.
I turned on Spotlight for every partition I boot into turning it off for the other two (e.g., if Mavericks is current then Spotlight disabled for the others). I do it every time I re-boot to one of the 3 partitions. After that Mavericks was able to establish connection with geolocation services and the function is rock solid since then.
Maybe that helps those of you who struggle to get it working. Try running metadata processes by re-indexing your drive and make sure it's the only bootable partition or, if it's not, that Spotlight is turned only for the current bootable partition.
I'd be interested to know if this suggestion rectifies this issue.
Update 12 Jan 2021
I use Squid proxy in Mavericks and Lion on port 3128 and have Spotlight enabled in both. I have no geolocation problems and to disable Spotlight indexing every time I boot from either of these partitions I put a special hidden file in the root folder of the file system.
ALTERNATIVE SOLUTION #2
MORE LIKELY TO BE THE REAL ONE.
I suddenly started to have this problem in Lion that along the course of 7 years I use it never showed it but managed to reproduce and solve. To make long story short: if the problem can't be cured by re-indexing the volume the chances are it could arise from a corrupted database cache file in one of lower system-level folders owned by a process named "locationd". The specific file I'm referring to is a database file cache.db. In Lion, there's a folder at the path /private/var/folders/zz/zyxvpxvq6csfxvn_n00000sm00006d/C. Inside the folder, you'll find clients.plist file that contains information about every process and application granted access to the geolocation services and several db files, cache.db included. The problem is that macOS doesn't update it properly if you uninstall an application that had previously used your Mac's geographical position. At the GUI level you see this as a blank icon of the uninstalled application in Security&Privacy settings of System Preferences. Changing the plist alone by deleting corresponding values doesn't lead to the auto-update of the aforementioned
cache.db file but causes the OS to lose tracks of the location, hence "Your location is currently undetermined" message when you're in "Time Zone" section of "Date&Time" settings pane. The solution is to delete the cache.db file too and re-boot (the reboot is important). After that it may take some time for the system to rebuild the cache.db file but now your location becomes detectable and the red pin is positioned correctly. It now lets applications use your location seamlessly.
Beware that all above pertains to Lion. In the newer releases, the location of "locationd" files and folders may be different and so can be the database file names and their count inside the containing folder with a high probability so you have to investigate on your own: e.g., as of Mojave, the folder in question is at /private/var/db/locationd/ and inside there're hidden files with the "dat" prefix in place of cache.db. Use the following command to find the clients.plist file which would point to the enclosing folder that you can open to look inside for cache.db or similar types of files. The command is
sudo find -Ex /private/var -name *clients\.plist
Replace yourhomefolder with the actual name of your home folder.
Filter the output out: you need only those entries that contain clients.plist. Look closely for the folder it's contained in.