Because the earth isn't a sphere, the common length-on-a-sphere great circle distance equation isn't perfect for the earth. However, it's a lot faster to calculate than the haversine length, which takes into account the squashed sphere that we live on.
We were calculating driving routes at high latitudes. The difference in the length calculation meant that east-west road lengths were being calculated as slightly longer than they really were.
Amortized across a long-distance route, this led to the mysterious tendency of the shortest-path algorithm to prefer north-south oriented roads a lot more often than you'd expect.
While we knew we were using the less precise great-circle distance, the deviation is not all that big, so we didn't really expect the difference to manifest in the output.
Those were some mysterious detours.