The only way I've ever found to get around it is to cheat up Outdoorsman. For a non-cheating solution, there doesn't seem to be as many encounters on direct routes to the missions. So another option might be to avoid wandering much and travelling straight as you can in speedy vehicles until you can get your skill up.
Don't know if it was intentional, but it DID make Outdoorsman a valuable skill.