I'd been using an "all players in the lead element roll, any trailing players automatically succeed" mechanic. So if the dwarf in plate mail hangs out behind the three sneaky players, the three sneaky players in the lead are the only ones who break out dice.
Then, I wasn't using Passive Perception as the DC, for each encounter I've been writing my own "Stealth DC", maybe something like this:
Situation: the party is walking down a corridor which opens into a hallway; there is no door.
Stealth DC 12: The lead element of the party reaches the last square of the corridor without alerting the orcs inside. Place the rest of the party in marching formation behind him, and the party have a Surprise round over the orcs, who all have their weapons sheathed.
Stealth DC 8: While the lead element of the party is about 20' away from the room, one of the orcs hears something: the party can hear him call out an alert to the others. Place the party in marching formation beyond, and neither side has a Surprise round.
Stealth DC <= 7: The party's noisy advance has given the orcs plenty of warning. The orcs draw their weapons and try to hide out of sight of the corridor. Place the lead element of the party in the last square of the corridor, with the rest of the party in marching formation behind him. The orcs get a Surprise round. Have the party make an active Perception check against DC 15; those who make the check also participate in the Surprise round.
... I adjust the numbers based on experience and the party makeup.
The idea of changing that to a Skill Challenge is actually pretty interesting .. I may have to toy with that a bit; I particularly like how, for example, a 6 success before 3 failure challenge does allow the not-so-stealthy dwarf to fail without unduly punishing the entire party for it.
