1. Make the prison 'sentient'. Have it evolve itself to combat attempted escapes. This could be an 'undermountain' effect in that the 'floorplan' changes - suddenly the exit has become the entrance to 'C-Block'... Door automatically open/close, lock/unlock - unwittingly leading the escapees back to their cells... etc, etc. It could even come with it's own automated defences.
2. Make it self governed. There was a PC game - Gothic, I think - whos story was that ill-doers get thrown through a 1-way portal to a prison plane/planet. No guards, no cells, no nothing. Just criminals - whom being evil provided all the punishment themselves!
3. Make it a 'alien'. Change everything from the normal campaign on it's head. That should provide both enough interest & confusion to your players.
4. Soul bond - This is 'hijacked' from a game I'm currently playing on these forums. Upon entrance to the prison (us PC's - 6 of us) have had our souls bound to another inmate. The group has LG & CE characters, yet they work together because they know that killing one of us would also kill another - whom, we don't know!
5. Have the only prison exit lead directly to the lowest levels of the abyss... Do not pass GO and do not collect $200...
Hope they help a little...