It's a goddamn role playing game. If you want to be a very good fighter you'll have no poins for the outdoorsman skill. That's just how it is. Increase the skill or deal with the fact that you have many encounters.
I'm talking about chaning this skill from something not only 0 and 1. May be if you have middle outdoorsman skill you can't use it properly if you have people on your party, so leader should have alot outdoorsman, but if you're alone, you need alteast like 100-120% to avoid encounters enough, because it's like repair now, raise it on max or don't touch at all, because middle skill will do nothing and will work like minimal.
Edit: or make sneak+outdoorsman check if you're the only one without anyone in party, without mercs, slavesm etc. So these two skills will work together.