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 but that is to be judged on per-user basis.
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. 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.
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.
Update 12 Jan 2021
I use Squid proxy in Mavericks and Lion on port 3128 which translates insecure http queries to secure ones using the most recent TLS generation, and Spotlight is enabled in both. I have no geolocation problems and to disable Spotlight indexing every time I change a partition I put a special hidden file in the root folder of the file system.
ALTERNATIVE SOLUTION #2
I suddenly started to have this problem in Lion, which 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. In the GUI level, you see this as a blank icon of the uninstalled application in Security&Privacy settings of System Preferences. Modifying just the plist by deleting corresponding values doesn't result in the auto-update of the aforementioned
cache.db file but causes the OS to lose tracks of the location, hence the "Your location is currently undetermined" message when you're in the "Time Zone" section of the "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: 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. Run the following command to find the clients.plist file.
sudo find -Ex /private/var -name *clients\.plist
The output points to the enclosing folder that you can open to look inside for cache.db.