no percentage.

how many times do you THINK they should encounter these dire creatures over the course of this plotline?

how many sessions will this plotline encompass?

do some division and you're done.

I agree with tobyspit to a point: you decide. Don't leave it up to a percentage, but instead decide what you want to teach the players about the world around them and then attack them until they know what you want them to know. But I don't think that's what you're really asking.

I like the idea of roleplay and build character first. Period. Above all else in my games I let the players live otu the lives of their characters. Fighting is fun, but it's also not the focus of the games I run or play in. It can get in the way of a plotline, though, or even derail it at times.

Is the spell supposed to lead them around dangers, like Find the Path or something? I would avoid having a fail percentage in a spell you gave them, if that is the case. It leads to a lack of trust. But it's possible these creatures can simply be seen along the path, even at a slight distance, might that work? You're trying to show them how bad things are, right? So they can see that at a distance, or even have the creatures simply ambush them.

The spell is supposed to lead them places that they've never been before, through territory that they'd otherwise be unable to traverse. The NPC who taught them the spell mentioned right off the bat that it may fail from time to time, so it shouldn't lead to a trust issue. They've also been able to withdraw from the handful of battles they didn't actually want to fight.

I really like the idea of them seeing larger creatures from further off. Thanks. :)

Since the above responses don't seem to be the sort of help you're looking for:

15%

If you're banking on the potentiality of random encounters when you've already got encounters established in the story, I wouldn't stray farther than 15%. I forget exactly where I grabbed that number from originally, I think it may have been something to do with Wandering Monsters in dungeons.

In any case, 15%. It's not high, but it's not all that low either.

To be fair, if you're introducing such random elements like this (which I whole heartedly approve of) you should also be prepared with a table to facilitate true randomness. For example, the DMG suggests that 5% of all encounters should be "Overwhelming." You probably don't need to include these in random encounter tables, as you should have them worked into your storyline.

As a general rule of thumb nothing random should be more taxing than anything the party encounters over the course of the plot.

It should also be noted that random encounters need not end in combat. Depending on how your players handle the situation, it could be as simple as "Holy crap, a dire weasel!" and they continue walking.

Yeah, I'm tossing some ridiculous things in there as well. I've been dying to apply the half-dragon template to something silly for a while now. :) And like I said above, they've been pretty good about getting away from the encounters they'd rather not be part of.

I agree with the idea the DMG's putting across, but I think it's built into CRs already. Tonight the group fought two things - a Colossal Centipede (CR 9) and a Hellwasp Swarm (CR 8). They tore into the Centipede with barely any trouble, having some really decent damage-dealers on board. The Swarm, however, nearly pulled off a TPK before they got their act together and managed an orderly retreat. They just didn't have the specialized attacks (non-weapon, non-fire magical area attacks) that were needed to bag the Swarm.

Another way to think about it: do the players have any way of avoiding the failure? Does failure come about because of some actions on their part? Or is it just "15% chance and you fight."

If the players were trying to follow a path in a way that was supposed to be difficult (I'm thinking 4e Skill Challenge type thing here), then the "failure chance" is the chance that they mess up. Ie, if you wanted a 25% chance of failure set it up so they have a 75% chance of making their actively decided upon rolls or whatnot.

"You guys get into a fight because I rolled a 3" is pretty boring. "You guys get into a fight because the ranger failed his survival check and the fighter flubbed another stealth check" is more fun--though all the normal good gaming rules apply (such as letting players try and recover from errors and allowing creative ability usages and stuff).

Fortunately, the mechanic's actually doing exactly what I want it to with this particular group. I've asked them about it, so they know how it's being done, and they're enjoying it. I don't force them into a conflict, they can (and do) use their skills and abilities to bypass conflicts they don't think they can handle or just don't want to deal with.

Maybe it would have been more to the point to ask how often people insert "mini-boss" or "non-BBEG" combat-possible encounters into their campaigns?

For the sake and fun of debate, I don't think the mechanics are much different than those of Arcane Spell Failure. I don't see how this is any less an "actively decided" roll than a caster casting Find The Path in, say, a Breastplate. If the spell fails, they still end up someplace other than the intended destination. In a hostile region, that more than likely means running across something hostile. :)

I'd put it along the same lines as not being able to Take 10 on a roll intended to move the game along. Sure the failure in and of itself could be interesting, but it doesn't necessarily add anything. Depending on your players (if they're, say, like me in some of the more tedious games I've played), the delay of the fun parts of the story might negate any amusement coming from the diversion. Again, it depends on your players group and campaign, but it's something to consider.

(And if the players are rolling a check, then at least they're doing something, so the "screwing up" is happening on their end rather than on the DM's).

What might be best is to do a wrinkling thing: "you following the path, but occassionally it leads you astray. You run into the following distant encounters you can deal with as you want" kind of thing. That way there is a sense that the magic isn't perfect, you can include exactly and only as many interesting encounters as you want, and it doesn't feel like the characters are being held back from the story by bad rolls. In other words, don't make it random, make the failure part of the game. Unless the randomness is because of the players. Nothing the DM does should be random IMO, particularly for the story.

But that's my play-style--as I said, your group might differ :) And really, you know your group better than any of us, so the answer is: as many/often as you want/feel is fun :)