I don't see how this situation can end well with the current party dynamic.
The guards appear to be the rightful law, there is no indication that they aren't, and any attempts to discern anything about them have failed. Therfore I am bound by paladins code to abide by their laws.
Albedo's exalted character has similar restrictions, and neither of our characters will allow the guards to be slaughtered because of the pride of a seemingly evil demon.
I have, in fact, gone out of my way metagaming to try and prevent a fight with the marilith allready, but there is no indication that she could be good. Shahaza claims not to be evil, but her actions are just as bloodthirsty as Dizzy's (Who also seems fairly intent on violence), and so far there's nothing in either of their actions that indicates they're good.
The guards, also, are not helping, as they have shrugged off every offer of compromise and are insistant that the PC's be shackled and arrested. As I stated before, If there were some way of telling that they're Evil, Kayla would resist them, but she has no reason to believe that.
The ironic part is that if not for the fact that people spent so much time becoming immune to non-lethal forms of combat such as Holds/charms/Grapples/etc, I might have been able to stop it.
Well, I guess it's up to Neph/Albedo and the DM.
*EDIT: Actually, I do have ONE idea I'm going to try, it's a bit out of character but its' all I can think of.