Here's an evil idea...
Iuz, like most evil overlords, uses evil lieutenants. Now, there are advantages to this--no suddenly squeamish consciences, no crippling attacks of remorse, no problems with casual torture--but there are also problems--loyalty is generally low. Oh, sure, there are your priests, but even those guys tend to be a little less than utterly devoted to you--and seeing as that's thier job, you know you've got trouble.
And there are others--evil wizards, assassins and warriors who'll serve your beck and call, all the while trying to serve their own interests even more. The only way you have to keep them in line is to make them so afraid of you that they don't dare betray you. And losing isn't a good way to do that...
So now, Iuz is losing his hold on Tenh. But a lot of his lieutenants are still in the region. And yes, many of them are going to be writing home to Iuz and making sure the bad work continues. But at this point, a good chunk of them are going to thinking about how to flee a sinking ship with as many valuables as they can carry.
Some will of course join up or start low-level crime syndicates, mercenary companies, and the like. But a few of your more ambitious ones might think they have a chance to become a power on their own. Of that group, some might try to serve the Liberators heads up on a platter. But one with the right amount of cunning would try to cut a deal with them--aiding them in their efforts to defeat Iuz in return for rule of a city, or small region. This offer should come at a time when the characters are slightly (or even very) desperate. The characters will then face a choice--accept his aid, and the devil's bargain it brings, or refuse it, and face failure.
Given the way the Liberators handle things, it'd be interesting to see how they'd react to this...