Sorry, crazy week or so, or I'd have been by sooner.
Anywho, let's start with our 'employer'. An advanced Yugoloth, eh? Well, we know that 'loths generally have little regard for anyone or anything other than themselves, and are as likely as not to honor their agreements. However, if Asomdeus is monitoring the agreement, then theoretically the 'loth MUST honor it, no matter how much he tries to twist it.
The trick here is that 'loths are KNOWN to be liars who don't hold to contracts terribly well, and any creature like a 'loth will be assumed by the party to be preparing to betray them. There's simply no way to suprise them with a betrayl...unless you've exhausted them, they're simply waiting for the moment of his deceit (and may have planned for it, in some way).
This is where you join us in the RBDM club.
First off, let's step back for a second and examine our position. The PCs are locked into a contract to serve Khrel-Hadad for the next X days. In that time, he's using them for his own ends, particularly to interfere in the battle of Lolth versus Pauzuzu.
This takes us to the plane of Caceri, the prison plane.
First: there are two kinds of people on Carceri: those who don't want to be there and......um.....OK, there is only just the one kind. Let's rephrase, shall we? There are only two kinds of prisoners on Carceri: those who can't escape, and those who can't be
allowed to escape.
For set pieces, use various parts of the environment to creep the players out. Remember that, with one noticable exception, everyone they meet will be a prisoner or guard (and that the guards really don't want to be there, either). PCs will be much more creeped out by sights of petitioners being tortured than by of evil monsters. For example. you could show some 'eternal torments' in progress, in the vein of Sissyphus or Proteus. Imagine coming across a man who pulls himself out of scalding hot lake, his skin horribly burned, scarred and puckered. Around his neck and ankles are long chains that lead back into the lake. He starts to heal, as the PCs watch, and seems to breathe a sigh of relief (perhaps even talks to the PCs or imparts information). Suddenly, he's yanked back in to the scalding lake, screaming in horror and pain...as he does, every five minutes or so. You get the idea.
Also, use the pure alienness of the place to unnerve the players. Use things like odd images, strange architecture and ambient sounds and atmosphere to enhance the experience. Make sure and emphasize what an unpleasant and unwelcoming place Carceri is. If they have to sleep there, make sure they have bad dreams of being trapped, of suffocating or perhaps something specific to the character. Show them the hopeless nature of those trapped there, and the PCs inability to save the damned (at least, on a macro scale).
These same rules apply to the Abyss, but have the tortures and specific differ. The idea is that the planes are a hostile place in many ways, some not purely physcial. With high level spells, PCs can ignore many of the detrimental effects, but not the emotional and spiritual ones. Remember also that pure gore and shock wear off, so use it sparingly...and also gauge your players' tolerance for such material, as well.
Cynosure/Sigil: (Loved Grimjack, btw). Play on PCs perceptions, here. One of the thing that makes Sigil so effective as a setting is that, since deific intervention is blocked, celestials and infernals have to share the same space, glaring at each other over veiled threats. The unusual is usual in Sigil, a veritable 'Casablanca' on the D&D world. Sigil is a crazy place, with it's own odd rules that don't make sense qute often. One could easily argue that Cynosure was the inspiration for Sigil, although I'm sure Cynosure is probably inspired by Zelazny or someone else.
Make Cynosure a mixed-up place, where the impossible seems ordinary to the residents, and things don't make sense. The PCs should feel, after a fashion, that they're walking through a mental asylum part of the time. Doors appear and disappear. Buildings move. Gateways drop people and things from out of nowhere. The beings who maintain the city are inscruitable and unapproachable. The Lady of Pain IS the city, in some ways, and I'd recommend something similar for Cynosure, even if it isn't as personified as the Lady. Focus the group on being out of water and being looked on as clueless newbs or rubes by beings far less powerful than they are. Consider that a street urchin in Sigil knows more than the PCs, and that a tout (guide) in Sigil is a must for non-residents (and some residents, too).
Now, as for rewards....as I said before, the PCs are just waiting for the betrayl. The only thing they don't know about is the when and where. Trip them up, and do something they're not expecting.
Have their supposedly final mission to be to inconvience, trick or somehow muck about in the affairs of one of his betters. Suppose that K-H decides that his time to become something more has come, but he needs to make a vacancy above him? He sends the PCs to procure an item from his leige-lord, a
BEARNOLOTH. Let them succeed in the mission, but be discovered in the process, and
have to run for their lives. Make it a panicked, tense "he's coming! RUN! What do we do now? " sort of situation. Don't trap the PCs, though, or force their hands to defend themselves (i.e. don't back the paladin into a corner, where he feels he has to make a stand).
Now, have them return to ol' Khel-Hadrad with the item, and then have the Bearnoloth show up and crush him. How does it play out? That's up to you. Could be that they fight each other to a near stand-still...and one falls. The PCs now have to finish off the victor, if they hope to survive and escape. Could be that one has an ace up his sleeve, and destroys the other. What he does in his victory is up to you.
Take away some of their moral certitude, even in their victory. Lie down with dogs, and get up with fleas. Zad is very correct, though, in that you should not punish the paladin or force some sort of atonement moment on him to survive or win. Sacrifice, perhaps, but not that. Give them a chance to be noble, if possible. Even better, give the paladin a chance to scold the wizard with a "I told you so" moment.
You could even use this as a way to extend some of their planes-hopping.
Give me some time, I'll think of more.