Hey Parker,
I'm running a West Marches style game right now - we're 8 sessions in I think - the characters are all level 4 (except for one who's only made 2 sessions).
Obsidian Portal link if you're interested (adventure log a couple sessions behind - the map is a bit behind as well):
http://www.obsidianportal.com/campaigns/explorethefrontierFor Undertakea Perilous Journey, I have them roll if they're moving through unsecure ground. For instance, the Eldar Plains in our campaign is probably the only area that is safe and I wouldn't have them roll. If they took out the bandit mercenary company they know is making camp in the Unnamed Valley then that would perhaps become safe as well but they haven't quite done that yet.
I usually have them roll for the entire journey up front (so if they're travelling through 3 areas it would be one roll). I typically make them use up 1 use of food per area as well. If they fail the roll and I choose the "use up their food option" that typically is either 1 whole ration (all of its uses) or all the rations they're carrying on them (they usually have a horse and cart with extra supplies for long journeys and I don't use those up typically).
If you have any specific questions on how we're handling things ask away.