This is more of a warning than a help to fix it, because I already got past the issue.

I was going through Level 2 of the dungeon, clearing everything except the water temple (not on purpose, it just happened this way), and was on my way to clear that section last.

As I was bull rushing my whole party towards the water temple priest Belsornig and the juggernaut, a dialogue with Belsornig automatically initiated when my characters got close. In the dialogue, Belsornig was impressed that I already killed the fire temple priest Alrrem and the troll chief Oolgrist and was complementing my deeds. The only dialogue option available to me in response was to demand payment or something along those lines. No other options were available. Selecting that option automatically makes my paladin fall.

I was lucky to have saved just before attacking so that I could reload. I tried approaching with different characters, and found out that some characters initiated combat immediately while others initiated the paladin-falling trap dialogue. Even the paladin herself! Perhaps it has something to do with alignments, races, or diplomacy skills, but regardless for anyone trying a no-save/no-reload run, this is a heads up for you.

The rules for fallen paladin are ridiculous. They creep up everywhere. If you don't say "bless you" when someone sneezes, AH fallen paladin! Actually, I remember getting fallen from participating in the drinking contest at the tavern. Fallen? Really? Maybe a superior would tell me to knock it off but...

Yeah, this game is pretty strict with paladins. In this instance though, the dialogue definitely shows questionable judgment on the paladin's part by demanding payment from an evil cleric for killing other evil guys. But the real issue here is that there's no way to get out of the dialogue. There's no "No thanks, I'll just kill you too because you're evil" option. Plus it's not even that I initiated the conversation, it happens automatically upon nearing the NPC. The only way to avoid this is by hoping that the closest PC just happens to trigger combat rather than conversation, or by starting off hostile from afar to override any potential for conversation.

I guess a true paladin would snipe his enemies rather than face them in a headlong charge, haha.

Definitely true, it's a bum deal to have no choice but the one evil path.

However, even an "evil" decision like that is subjective. I've heard DMs argue with Paladin players about what evil is. This one player wanted to murder some tied up bandits, because they had to leave, and the bandits would probably free themselves to murder more innocents. Ultimately, the DM still considered that evil. But the fact is it's a gray area. And being fallen certainly should NOT be invoked by such petty dialogs. At least have it be something heavy!

I guess what I'm trying to get at is, ToEE's design in that department is heavily flawed. If they hadn't messed that up in the first place, there'd be no worry about being stuck with such a bad decision.