Nor does the next one. But maybe some of these tasks aren't quite what they seem, or maybe the characters don't even realize they are working for a devil. Perhaps the characters are confronted by a group of people who work for an opposing faction, perhaps even the henchmen of other devils. Or maybe some angels desperately want to stop anything that this devil wants to do.
Devils will hit where it hurts when betrayed, too. Be sure to play up the vengeance aspect of the devil if your players turn on him. Try to get them to really hate this devil, and they'll want to get back at him.
Or maybe they try to enlist with the forces arrayed against this devil, and there you go - mercenary heroes.
Or let something very powerful fall into your players hands, and devils want it badly. Suddenly they have a valuable item, which as greedy mercenaries they want to keep to sell to the highest bidder. The devils, being impatient with these impertinent mortals, will simply try to kill the characters and take it.
You could even go with the go old "characters have their souls stolen, but have X amount of time to get them back." The devils have taken the souls to their hideout to perform terrible rituals on them and gain power over the characters.
There's plenty of ways to use devils, and have fun!
I would also say that the War Devil would be a good one to tinker around with, adjusting his level to near that of your adventurers. He could lead another mercenary band that is pillaging nearby towns, and those towns need mercenaries to take them down. Perhaps he is even acting on orders from a Pit Fiend in the Nine Hells, trying to create discord so that there is a safe launching point for an invasion.
Maybe the devils are trying to set up an open portal from the Nine Hells so they can just march armies straight to the Prime Material Plane. Maybe even the only way to shut it down is from the other side, so someone (the characters) has to get through. A local powerful wizard could even promise to teleport them back from the Hells if they can close the gate, with some magical items he'll create when they get back as a reward as well.
Hey, depending on how mercenary your players have been, maybe this wizard is lying, and he figures he'll take care of two birds with one stone. He lies to them about bringing them back and they go to shut the portal down. There, now they're stuck in the Nine Hells, and have to get out somehow.
I mean, these are all just vague ideas. You know your players better than I do, so try to create situations where they devious, soul-greedy aspect of devils comes through if you think they'd like that, or even go with a more inter-planar raiders angle. The succubus is a great villain, especially when included with a murky political landscape.
Again, have fun!
EDIT: And, of course, MusicOfCreation has another good idea. If you don't know what that picture is, look up "Lemarchand's box" on wikipedia.
The PC have been tasked by the succubus (without knowing it) to retrieve the box. The succubus tells them it is an ancient relic from an old religion, and she would like to retrieve it( in exchange of course of money).The box is actually in the ruins of an old cathedral, and can only retrieved by creature who are not tainted by evil. The succubus intend to use the box to send more souls to hell and to bring more and more devils in the material plane with it. So here's my last questions:
1- How should I design the way the box work? Maybe my players will try to use it just to see what it can do just after finding it. It would then be good that I know how they are suppose to solve it. Maybe a skill challenge? If yes, what is the complexity and the key skills?
2- What kind of creature should be found in the cathedral? I intend it to be a forgotten shrine of devils, so should I just put devils? Actually I have two lv 10 players and 3 lv 1 players. Yeah, I know it's kinda odd, but it's like if I was having a 5th lv group.
Some maybe helpful tips: Be sure to have an explanation as to why there are evil creatures in the cathedral if non-evil people are needed to retrieve the box. Perhaps the devils in the cathedral are trapped inside by the same magic that keeps other evil creatures out? The box itself would also have to be kept warded in this case, so the creatures inside cannot get to it and manipulate it.
A skill challenge for the box sounds pretty good too. Try to make sure everyone can contribute something, so no one feels left out. It's easier to draw your players in that way. This could be difficult, though, as it may not lend itself to many skills. Arcana, of course, and Religion would be big ones. History would be good too, giving hints about puzzles or riddles to the characters that they can try on the box. Perception and Insight would also be good.
A forgotten shrine to devils could have more than just devils in it. Toss some undead in; they could have been used by the devils in times long past as guards or battle fodder. Ghosts as well as ghouls could work just fine.
You could even put in an angel - he's been guarding the box for centuries, but he can't escape with it alone. He could either attack the characters right away, thinking they are in league with the devils because he can sense the stink of the succubus all over them; or, he could try to talk them out of taking the box or even try to get them to help him leave with it. He could ask if they know of good hiding places, or nearby good-aligned temples that he can go to and finally relieve himself of this burden.
Maybe, since this was an old shrine to devils, some of the vile energy from the Nine Hells has leaked across to the Prime, and now normal creatures who took up residence in the shrine have been twisted by it. Some tangler beetles with some fire beetles, maybe a few rats or snakes with strange powers. Oozes can work well too.
Adjust a flesh golem to an appropriate challenge and stick one in. Anything can work with the proper spin.
That box could be key in undoing their curse, perhaps the will of the god writ when he/she was last lucid...or it contains the catalyst of his/her insanity. The reason they cannot collect it is because it can only be retrieved by one whose hands have not been stained by divine blood (as a security measure against it being stolen by other divine beings).
Take it a step further and say hands stained by any blood; the PCs must escort a child there...
Other celestials, perhaps employing angels, are fearful of their deicide neighbors and would like to stop them from being able to travel the planes freely again. They would be willing to sacrifice too much for greater good and for their assumptions.
Really, not all devils need be evil....
One or more of them became dissatisfied with their lord (or the lord was destroyed) and turned ronin, finding refuge in the place now known as the Nine Hells. They are still shaped by their dead/betrayed master's ideas, wishes and fantasies and act accordingly. Asmodeus and the other archdevils are the leaders of the revolt or the survivors of their masters demise.