My party is about to explore Skull's Crossing and I was wondering how exactly the pit fiends bound to the dam suffered from any negative levels at all. A normal pit fiend gets a +24 on fortitude saves and it's only a DC 20 fortitude save to remove the negative level, so in the beginning they'd have to roll 1s to fail to shake off the negative levels. Considering the floodgates only opened 150 in the last 10,000 years, it seems both of the pit fiends would have plenty of time to recover in between floods to remove the levels.
Also, on a side note, couldn't a pit fiend with 19 negative levels still easily beat a party of 9th level PCs with its Sp. and Su. abilities?
Well, every negative level reduces your saves. A few unlucky rolls early on will make all additional rolls quite a bit harder. It's not extremely likely but totally possible for the pit fiends to succumb to that many negative levels.
There's also the possibility that they've been bound with their true name or special thassilonian magic that weakens them and makes them easier to hold but also lowers their safes a bit.
As for the SLA, the negative levels also reduce your caster level making them much less of a thread for a 9th level party. And besides, the remaining fiend is still bound by magic and shouldn't even have an opportunity to attack the PCs unless they do something to free it.