I spend a decent amount of time exploring strange parts of the world, and in my experience with several different phones in several different countries is that GPS (assuming your phone is charged and you're not in a cave/underground) is always good enough to get you out of wherever you are.
To give some examples, in the past twelve months or so I've navigated by GPS (using Google Maps to visualize my position) in mountains in Iran, semi-rural Ukraine, forests in France, middle-of-nowhere Canada, and forests in America. In case you think that my GPS worked just because I had good devices, I've used everything from a nice iPhone 6+ to a decent Galaxy S5 to a crappy Huawei P8 Lite which I bought for $65 used.
I'm not sure how you can quantify GPS as "80% accurate". Does that mean 20% of the time it puts you in the next state over? Or that it's 200 meters off? I can't think of a reason why your GPS position would be wrong... it's not as if physics just breaks down in the Rockies.
In order to get such tremendously poor results, I have a feeling that you did something like turning off GPS (which forces your phone to rely on cell tower triangulation) or using GPS where it doesn't work (like in a cave.) If the actual, raw values from your GPS were wrong I would be extremely surprised.