Update: I'm working on a skill challenge should the party try to infiltrate Mentiri, the dreaded prison of Dis, to rescue a captive paladin. As a model for the challenge, I'm using Mike Mearl's "Moving Through Suderham" from DMG2. This is still a work in progress, and any feedback is much appreciated...
Infiltrating Mentiri
Skill challenge, 12th level, complexity (special rules); 3,500 XP
As the PCs infiltrate Mentiri, they explore the infernal prison’s bastions and cells in an attempt to locate Temerin, the captive paladin. This skill challenge doesn’t have a finite success or failure condition, but instead determines what sort of opposition the PCs face as they explore. There are five areas in the prison (described below): the Labyrinth, Bastille of Flesh, Bastille of Souls, the Oubliette, and a Secret Escape Route.
Strategies
The PCs can pursue 3 basic objectives that drive this skill challenge: travel within their current area, travel into a new area, and gather information. A variety of skills encompassing stealth, distraction, disguise, sabotage, leverage, and more can be used; the DC of checks is determined by the current alertness level.
When a group skill check is called for, it requires half or more of the PCs succeed for the group check to count as a success. For these group skill checks, let the players use different skills corresponding to their strategy; if one PC uses Stealth to evade the devils and another uses Endurance to hold their breath in a duct filled with poison gas that’s out of sight, they can both make the same group check (so long as they share the same objective).
Travel in Current Area
A group skill check is required to move through an area of Mentiri without incident. Success means the PCs arrive at a new spot within their current area. Failure means they have a random encounter en route.
Travel to a Different Area
Moving between areas of Mentiri is difficult because there are magic gates guarded by large numbers of devils dividing each area. A group skill check is required; though increase the DC by +2. Success means the PCs arrive in the new area. Failure means the PCs have a random encounter and increase the alertness level by one step.
Gather Information
As the PCs infiltrate Mentiri, they'll at least need to gather information about the paladin Temerin. Depending on the area they are in, different information can be gained (see the area descriptions). A group skill check is required to unearth the desired information without attracting unwanted attention. On a failed check, the PCs are either betrayed (increase alertness level by one step), attacked (roll on random encounter table), or fed misinformation, depending on the nature of their informant.
Alertness Level
Mentiri is crawling with devils, making it an extremely important that the PCs don’t drawn attention to themselves. The alertness level measures how aware the devils are of the PCs’ infiltration, how actively they are hunting the PCs, and how quickly they can mobilize patrols. The alertness level begins at low, unless the PCs were deceived by ?? in the Fetters, in which case it begins at moderate. “Extra enemies” refers to the number of extra enemies you should include with a random encounter.
Low: Stealth/Bluff DC 20; Default response is cautious, may mistake PCs for disguised half-devils or mercenaries, rely on passive Perception/Insight checks.
Moderate: Stealth/Bluff DC 24; add 4 legions devils to random encounters; Default response is cautious, attempt to learn about PCs before sending for reinforcements; make one active Perception/Insight check.
High: Stealth/Bluff DC 28; add 4 legions devils & a standard to random encounters; Default response is hostile, though the devils will try to take the PCs alive if possible; make two active Perception/Insight checks.
Maximum: Stealth/Bluff DC 32; add 8 legions devils & a standard to random encounters; Default response is hostile in the extreme, and unless supervised devils attempt to kill PCs; make three active Perception/Insight checks.