TL; DR: Running betrayal like this answer suggests, in my experience, leads to anger and despair. Instead, I run betrayal like normal combat, and I'm happy with the results. Although the core rules on running betrayal aren't 100% clear, outside the core rules, one designer provides guidelines that are similar to (but not identical to) running betrayal like this answer suggests.
Note: This answer is long. I hadn't realized when I began this answer the depths of my feelings on this issue, nor had I considered the position I staked out to be in any way controversial. Make tea, settle in, and know that the author appreciates your time.
This DM runs betrayal similar to a normal encounter
For years I tried this answer's solution but was dissatisfied with the results. You might not be dissatisfied, and that's totally cool. Further, were I a player in your campaign, and you picked to do things like in this answer or in a different way altogether, I wouldn't flip your table and storm off. Finally, I'm sure that other playable, fair, and fun options exist, and if one's working for you group, that's great. Seriously, if everyone's happy, keep on keeping on. I'm not judging. Your fun isn't wrong.
But in my campaigns arguments about how to run situations just like that described in the question were frequent enough that my campaigns needed a consistent, better solution. The one I implemented involved me not trying anymore to force what seemed to me the square peg of the merely unanticipated into the circular hole of surprise mechanics. Instead, I started running betrayals and other sudden events pretty much like normal combat, and it's worked out great for me. Here's how I do it.
Situations not meriting surprise
In situations like the question describes—like when Bob the until-now friendly wizard who's standing right there up and casts mass hold person on the PCs, or when a PC strutting down the street suddenly decides to stab a random nearby elf (as is a PC's wont)—I start an encounter as I would any other: players roll initiative for their PCs, I roll initiative for the NPCs, and everybody takes their turns in order.
If the creature that's planning to perform the sudden act has the highest initiative count, the creature goes first normally. For example, Bob casts mass hold person or the PC decapitates the elf. Other creatures involved are left to react to his sudden act afterward, but—unlike if a surprise round had occurred—those creatures react normally this turn, and they can take a complete round's worth of actions.
If the creature that's planning to perform the sudden act doesn't take his turn first, folks who act before that creature usually take the special initiative action delay unless they've an in-character reason or suspicion to take actions to try to thwart the creature (for example, the creature may advertise its intentions when it's not the creature's turn by taking a free action speak, Bob delivering villainous exposition explaining his betrayal, or the PC launching into a profanity-laced tirade detailing his displeasure with the tree-hugging, pointy-eared daisy-eater). Thus those folks usually take their turns after, for example, backstabbing Bob casts mass hold person or the PC lops off the head of a nearby elf. But, in the wake of an unadvertised event, on the same turn, those that delayed still get full round actions. More importantly, unlike had a surprise round occurred, there's normally no chance for the creature that performed the sudden act to take—totally unopposed—two turns in a row (the first turn being shorter, it having occurred during the surprise round).
Keep in mind, though, that in such situations this DM thinks it's okay for a player to have his PC take actions because the PC's a paranoid (but not necessarily mistaken) adventurer. For example, a PC having a higher initiative result than Bob and that doesn't trust Bob may spend his turn to take a move action to move up to his speed while drawing his bastard sword so that he's adjacent to Bob and take a standard action to ready a standard attack with the trigger If Bob starts casting a spell. This all despite Bob not having actually done anything! Similarly, another PC that wants to avoid trouble with the authorities and that's aware of the PC's propensity for elf-murder may take a standard action to ready the special attack disarm with the trigger If the elf-hating PC attacks the elf.
In sum, this process means I don't worry about, for example, removing player agency (see Why I don't determine surprise using DM fiat, below) nor about a series of Bluff skill checks opposed by Sense Motive skill checks (see Why I don't determine surprise using Bluff and Sense Motive, below). Instead, when an obvious nearby creature opts to do something unanticipated, things happen, the shock of the sudden act still resonates, and the creature still tends to act first and unopposed, yet the absence of the surprise round removes a potentially devastating advantage to behaving like a traitorous jerk or an impetuous killer.
Situations meriting surpise
Barring exceptions like the extraordinary ability lightning strike of the dire tortoise (Sandstorm 152), in my campaigns surprise occurs only when an encounter begins with one or more creatures unaware of the presence of one or more other nearby creatures. That's pretty much it.
Why I stopped using surprise for the merely unanticipated
I used to run situations like this exactly as described in this answer, but I stopped. There are rules supporting why I stopped—some, anyway—, and those are discussed below, but the real reasons are personal: I, as the DM, was uncomfortable with how declaring that a creature receives a surprise round for acting in an unexpected fashion removes player agency, and I, as a DM, disliked the tension created at the table when I used what felt like nonstandard mechanics for a creature acting in an unexpected fashion.
Why I don't determine surprise using DM fiat
I can't point at a specific example in my gaming history where I made the switch from awarding a surprise round for doing the unexpected to earning a surprise round by sneaking or lying in wait, but I'm pretty sure I started reconsidering after a situation like this:
DM: The hireling quick draws his dagger and attacks you, PC 1. You weren't expecting it. The hireling gets a surprise round.
Player 1: Aw, man, I never trusted him!
Player 2: Me neither.
Player 3: I always sort of liked him.
Player 4: O, too bad. That guy was great. He saved my familiar.
Before the hireling tried stabbing Player 1, I didn't really care what everyone thought of the hireling. I thought that the hireling betraying the PCs was the important part. Then, upon the hireling's betrayal, I realized it did matter what the PCs thought of the hireling, and it was too late. I considered retconning the event so that the hireling attacked a different PC who did trust the hireling, but with the reveal already spoiled I let the event stand. Then I thought Is it okay for me to have said that PC 1 was not expecting the surprise attack from the hireling at all?
I'm a conscientious DM. I take notes, keep track of NPCs and plots, and listen to my players so that I run campaigns both that I enjoy running and that players seem to enjoy playing. What I absolutely distance myself from is playing a PC. That's what the player does. I get to play the universe, and the player (usually) only gets that one PC. However, when I said, "You weren't expecting it," I played a PC. I make every attempt not to do that. I wanted the rules to support my efforts.
Why I don't determine surprise by first assessing trust
In Example A, I could've, beforehand, just asked the players about their PCs' attitudes toward the hireling and used that information to determine which PCs act in the surprise round. But Does your character find the hireling trustworthy? is a really loaded question that advertises in neon a later possible betrayal.
Further, if I don't immediately act on the information from my poll, circumstances and events may change how much the PCs trust the NPC! To keep things straight, I'd have to periodically ask PCs for trust updates on NPCs and record the results. Also, in case the sudden but inevitable betrayal is by the PCs (which—I know—totally never happens), I'd need to track how much I thought NPCs trust the PCs! That's a lot of work in my campaigns—which are usually sandboxes with hundreds of NPCs—, and it felt like my time could be better spent on other aspects of the game. So I didn't poll.
Why I don't determine surprise using Bluff and Sense Motive
Instead of either me saying what I thought a PC believed or polling the players on their attitudes toward NPCs, I tried for a while mechanizing unexpected actions (like betrayal) in a fashion similar to what this answer suggests. For example, upon deciding that the hireling was about to strike, I'd make a Bluff skill check for the hireling opposed by the PCs' Sense Motive skill checks. But it wasn't nearly as clean as it sounds, and I didn't like the results. We'd end up in situations like this:
DM: [The DM secretly makes the hireling's Bluff skill check opposed by the PCs' Sense Motive skill checks. PCs 1 and 2 beat the hireling's Bluff skill check's result with their Sense Motive skill check results, but PC 3 doesn't. The DM has Players 1 and 2 to roll initiative, and the DM rolls initiative for the hireling. PC 1 acts first, PC 2 second, the hireling last. Player 3, uninvolved for now, leaves the room to fetch a beer.] PC 1 and PC 2, the hireling has an evil glint in his eye. You suspect he's planning something shady. It's the surprise round. PC 1, it's your turn.
Player 1: Aw, man. I never trusted that hireling! Is he, like, doing anything?
DM: No. Not yet.
Player 1: So he's just standing there, and I get, like, a feeling?
Player 1: Whatever. I say, "Not so fast!" and take a move action to draw my greatsword.
DM: Taking a free action off-turn to speak, the hireling begs, "I didn't do anything! Please don't kill me!" It's your turn, PC 2.
Player 2: And the hireling's still just standing there?
DM: Yep. Well, begging there.
Player 2: Um. I guess, while I take a move action I draw my spiked chain and get the dude within my threatened area. I swing the spiked chain over my head threateningly and boom, "You'll pay for your insolence, hireling!"
DM: Okay. "I didn't do anything!" says the hireling. "Please, please, kind sirs, don't kill me!" The hireling takes a free action to drop to his knees and takes a standard action doing nothing but cowering in fear. It's round 1… round 2? Whatever. It's the round after the surprise round. [Player 3 returns, beer in hand.] Players 3, roll initiative. [He does. The order is PC 3, PC 1, PC 2, hireling.]
[Player 3 returns.] PC 3, it's your turn.
Player 3: Catch me up. What's the scene?
DM: PC 1, his greatsword readied, is adjacent to the hireling. PC 2, his spiked chain out, is 10 ft. from the hireling, the hireling within PC 2's threatened area. The hireling is prone, cowering and blubbering, begging PCs 1 and 2 not to kill him.
Player 3: "What's going on here?" I demand of… everybody, I guess?
Player 1: "The hireling was, like, going to kill us!" I explain.
Player 3: "How do you know? What did he do?"
DM: "I didn't do anything!" says the hireling.
Player 2: "Yeah, he didn't do anything," I say, "but we knew he was going to!"
Complaints started almost immediately, especially when the PCs tried the same tactic. I was asked things like Why's it a Bluff skill check when I'm stabbing not lying? and Why's the dude get a Sense Motive skill check when I didn't know until just now that I was going to make my random, totally unplanned attack? I made some counterarguments, but they were halfhearted: the process wasn't really withstanding my scrutiny either.
That's because I realized that, using the above process—unless the betrayer's on a clock and must betray right now—, the betrayer never actually betrays until he's positive the betrayal's undetected. And how does the betrayer know his betrayal's gone undetected? When the potentially betrayed don't act upon him considering the betrayal!
See, if the betrayer acts first in the surprise round, either the betrayer implements his plan if he believes the betrayal undetected (and, maybe, the other creatures, so as to not reveal they know what's up, must make opposed Bluff checks against the betrayer's Sense Motive check?) or the betrayer abandons his plan if he believes his betrayal detected (like if somebody yells, "Suspected traitor!" and stabs him).
And if, instead, the creature sensing the potential betrayal acts first in the surprise round, the creature can either act upon his knowledge even though the betrayer's yet to implement the plan, delay until after the betrayer's implemented the plan (which is pretty much what the betrayer wants anyway but worse for the betrayed because it's the surprise round), or ready an action with a trigger that won't get pulled if the betrayer recognizes he's been detected and opts not to implement the plan. (Readying an action does become a fairly comfortable option, but its efficacy here depends upon how the DM adjudicates others perceiving the creature that's readied the action: a betrayer may recognize that a creature's readied an action to be taken in response to his plan and, knowing that, abandon his plan.) In short, the betrayer almost always wins… or, at least, doesn't often lose.
What's worse is that I found this process sometimes putting everyone—including the DM—in uncomfortable positions. As Example B shows, what can happen at the table is this: the players and the DM know something was supposed to happen, and some PCs know they picked up on a signal that something was going to happen, but some other PCs actually see the initial PCs behaving like bullies, fools, or maniacs. That's a great role-playing opportunity… the first time. But after the situation's resolved (assuming the betrayer survives), when the betrayer again considers betraying, the process starts over, and it repeats again and again until, finally, either the betrayer gets both the surprise round all to himself and a really high initiative result or all the PCs sense the potential betrayal and (perhaps violently) cease their association with the betrayer (this despite the betrayer possibly still having done nothing!). Yuck.
While in the abstract this may sound only subtly different from how I run things now, in practice the difference is substantial.
Why I don't determine surprise using other house rules
Once I found a solution that worked for me, I stopped experimenting with other solutions. That means I've not playtested, for example, a house rule requiring an arbitrary, static Sense Motive skill check to detect betrayal—say DC 15?—, success indicating that the individual acts in the surprise round along with the betrayer. But even in the abstract, while such a house rule eliminates at least some disparity between low-level and high-level betrayers and betrayed since anyone can betray and sense betrayal, it places new emphasis on the skill Sense Motive: no one wants to be betrayed! Ranks in the Sense Motive skill or items improving Sense Motive skill checks pretty much become another existence tax on an already heavily taxed adventurer. There are, in this player's and DM's opinion, quite enough of those.
Thus I've thought about other house rules, but none of them seem better than the rules I use already, so I've not been motivated to playtest other rules since finding a solution that makes me happy.
"What about the rules?"
The Player's Handbook on Surprise (137) has 3 examples of possible surprise situations: in the first, foes are behind closed doors; in the second, foes hide; and in the third, a foe's hidden by darkness. The Dungeon Master's Guide on Combat (21-4) has 5 examples of possible surprise situations: in the first and fifth, the foe's hidden by darkness; in the second, third, and fourth, the foes are behind closed doors.
The examples and the full texts of the PH on Surprise (of which the SRD on Surprise is an excerpt) and the DMG on Combat (absent completely from the SRD) put everything about awareness in the context of awareness of a nearby creature's presence and never, for example, in the context of awareness of a nearby creature as a threat. And in the example encounters if the participants are aware of each other's nearby presences then the encounter doesn't begin with a surprise round.
The Player's Handbook on Surprise does say that the DM "may call for Listen checks, Spot checks, or other checks to see how aware the adventurers are of their opponents" (137 and emphasis mine). Similarly, the DMG on Starting an Encounter does say
When you [the DM] decide that it is possible for either side to become aware of the other, use Spot checks, Listen checks, sight ranges, and so on to determine which of the three above cases [for starting an encounter] comes into play. (21 and emphasis mine)
However, in over 1,700 words on surprise, neither text has a creature becoming aware (or trying and failing to become aware) of a creature as a threat after the nearby creature's presence is already confirmed. Only through those six words—or other checks and and so on—can surprise encompass such a betrayal. And if surprise is to occur when an obviously present and nearby creature suddenly becomes a enemy, and if such a situation is to be played differently from normal combat, exactly how to manage that situation is—beyond those six words—without rules and examples.
For this reason, this reader takes or other checks to mean atypical checks not usually required by other detection methods (e.g. blindsense, blindsight, detect evil, detect undead, scent, tremorsense). Further, this reader takes and so on to mean that the DM should use normally the game's other rules for standard and rarer detection methods. Given the context, that makes sense to this reader, and this DM's been happy with the results.1
Determining surprise according to one of the game's designers
Nonetheless, a reader may still hold that the game's designers just never considered what should happen when an obvious nearby creature decides to flip on its allies. Or a reader may hold that the designers did consider such a possibility; that awareness does, in fact, include awareness of previously detected nearby creatures that have not yet revealed themselves as threats; and that the designers believed that possibility so bizarre, implausible, remote, or perhaps even easily managed intuitively that no examples were needed to cover it and no additional rules were needed to govern it, and other checks and and so on being sufficient.
But Skip Williams—Monster Manual author and, with Monte Cook and Jonathan Tweet, one of the game's primary designers—in his distrusted-by-some Rules of the Game Web column in a 3-part series "All about Initiative" shows that the intent is, in fact, to have awareness mean awareness of a nearby creature's presence rather than awareness of a nearby creature as a threat. Further, Williams goes on to support, under specific circumstances, the possibility of a creature getting a surprise round even if all the creatures are already aware of each other's presences! Read on.
In "All about Initiative (Part One)", Williams explains how surprise normally works, saying
The rules leave identifying an encounter's start to the DM's good judgment. As a rule of thumb, however, an encounter begins when two groups are close enough to each other to perceive each other and at least one of the two groups has done so.…
- A group (or a single character) can surprise a potential foe by noticing that foe before the foe can notice them.
…At times, some creatures in a group will notice a foe when the others do not. In such cases, an encounter still begins with a surprise round, but everyone who has noticed the other group gets to act during the surprise round, though the acting creatures still are limited to one standard action each.
So, according to Williams, an encounter begins—combat music starts, initiative's rolled—every time one group notices another group and—importantly—vice-versa. Yet a group surprises foes by noticing the foes before the foes notice the group. (The article's context—in the next section, even—makes it clear that this isn't notice as in notice that the group's a threat but notice as in notice a nearby creature's presence.)
And, as promised, in "All about Initiative (Part Three)" on When Does an Encounter End? Williams says that a nearby obvious creature can receive a surprise round:
[T]he following condition… might signal an encounter's end:…
- Both sides agree to cease hostilities.
This could be a plainly stated agreement to stop fighting, or both sides might choose to withdraw from the battlefield (or at least put some space between each other).
Combatants could possibly effectively enter a truce simply by ceasing all hostile actions, [sic] but stand their ground. If an encounter enters a phase where nobody is attacking a foe and the two groups simply talk or observe each other, you might wish to declare the encounter over.… If the truce has held for about a minute and it seems nobody is inclined to fight, go ahead and declare the encounter over.…
A group that finds itself in a bad situation might want to feign a truce just to get the chance to jump the foe again.… A Diplomacy check that moves a foe's attitude from hostile to unfriendly (or more favorable) would do the trick (decisively ending hostilities). A Bluff check to put a foe at least temporarily at ease also would do the trick.…
It's usually best to skip the surprise round when the action resumes after a break in hostilities. If someone has really managed to hoodwink the opposition and has made them lower their guard, however, a surprise round might be in order. In such a case, the deceitful character (and any allies who are in on the ruse) should be the only character (or characters) who act [sic] during the surprise round, even though many other characters at the scene are aware of their foes.
(Emphasis mine.) To summarize, Group A and Group B notice each other, signalling the encounter's start. Hostilities ensue between Group A and Group B. Then Group A and Group B make peace, either by both groups agreeing to a truce; by, say, Group A using the skill Diplomacy to change the hostile attitudes of Group B to at least unfriendly; or by, say, Group A using the skill Bluff to hoodwink Group B into believing that hostilities have ended.2 Then, later, if, say, Group A hoodwinked in such a fashion Group B, the DM may rule that Group B's trust in Group A is so vast that Group B lets down its guard so that, when Group A attacks—despite Group A being nearby and in plain view—, Group A's earned an automatic surprise round.
Although these rules seems to apply only in very specific situations, a case can be made for applying these rules more broadly, including the situation the question presents. I suspect that most DMs don't roll initiative every time the PCs and a new group get within spotting distance on city streets, for instance. Instead, the PCs and the new group notice each other and opt not to engage in hostilities, a truce having been reached quickly and silently, yet neither side lowering its guard. However, when the PCs and Bob the wizard notice each other, hostilities are averted as Bob convinces the PCs of his trustworthiness via a Bluff skill check—maybe made months ago in game time! Should the DM determine this makes the PCs lower their guard around Bob, when Bob later betrays the PCs, Bob—according to Williams—gets a surprise round automatically.
Before researching this answer, I had no idea these rules for betrayal existed, and now I'm that sad they do. These rules would have me use both processes that I already tried therefore already know don't work in my campaigns.
Speaking from experience, I can't endorse these rules for betrayal despite their provenance. I can't in good conscience encourage others to use rules that at my table have led to arguments, and I certainly won't go back to ambushing PCs and telling them, "You weren't expecting it."
1 The extraordinary ability scent (MM 314), for example, normally doesn't require any checks to detect direction to creatures within 30 ft. nor checks to pinpoint a creature within 5 ft. Nonetheless, a DM may rule that a creature needs to make, for example, a Wisdom ability check (DC = whatever) to use scent effectively in an abattoir, perfumery, or sewer.
2 The skill Diplomacy only allows a creature to "change the attitudes of others (nonplayer characters) with a successful Diplomacy check" (PH 71 and emphasis mine). This makes PCs immune to die rolls seeking to end hostilities unless the NPCs are lying. Kind of a dead giveaway there, no?