Lela - very impressive.
You read the posts, and passed the test.
Seriously.
It's very easy for someone to assume they're right, and not look at their position ever.
It seems to me that you have the right balance for your game.
And from your post: It's Number 1.
Except its not just a small indiscretion, it's NOT an indiscretion.
You and others have convicted the PP of breaking & entering when he actually did nothing close to that.
Let's replay the scene:
Group talks to secretary, who's not letting them see NPC.
This NPC just talked to them with a
Commune, so they have an In-Character reason to believe she wants to talk to them, and they are being respectful and opportunistic in showing up personally.
One of the party has an idea, asks for Paladin to use his skills to distract female NPC.
PP tries out his skills, has a good roll and roleplay.
PP has to go to bathroom.
PP comes back, and goes out of his way to stop the other player because his Paladin would not like the sneakyness.
The PP didn't even know the door was Held. (Yes, that's a big plus FOR him, not against).
He stopped the party from continuing down a path that would even hint of impropriety.
And remember one important thing: in character, it only took the Paladin seconds to stop the situation before anything happened.
You later said that Elistreae was pissed they got in.
But you said they couldn't get in.

That's confusing.
And don't be treating this like a modern-day breaking and entering- that's meta-gaming and misrepresentative of what happened.
1, they didn't break in to anything before the Pally stopped them (right?) and
2, this isn't exactly a helpess female taking a shower that they're peeking in on - this is a goddess, who not only should have been open to talking with them (the successful Commune), but has more than a door to keep people away.
While you may be right in recognizing that it was close for the PP for a minute, he quickly rectified the situation. And remember: the Pally actually didn't do anything other than talk to a secretary.
In the end, in my experience, you really should only be holding actions against the Paladins that they actually do - not every possible ramification of their actions, otherwise playing a Paladin is practically impossible.
And I'm with you, in the camp that says that Paladin players should be held above normal character's actions.
Maybe you don't know about my background on the boards, but I've been a staunch advocate of Paladin-player Responsibility, arguing that Paladins can't just kill every evil they see, and they are not off the hook as long as they simply fought 'gainst the Evil.
However, in this case, the Pally didn't let an innocent die in his pursuit for bloody revenge.
This Pally didn't kill orc babies, or surrundered captives.
This Pally simply stopped his companions from doing their proposed course of action, which was simply to get in to see a supposedly-willing goddess so she could help their captive companion.
How does that rate a revoking of status?
It doesn't.
How does that rate even a loss of powers, however temporary?
It wouldn't.
Paladins are not machines that you wind up and set in motion.
Paladins are living, breathing embodiments of the ideals of a diety, or a concept.
Most people have difficulty thinking as a Paladin, since they are tough to play because of all the 'rules'.
Many people (IMO) should not play a Paladin because of this difficulty, and because of many people's inabilities to take on another persona who sees things in a bigger light than just actions and loot.
This PP did it right.
While he didn't instantaneously object to talking to the secretary, it only took him a couple seconds to stop the thief.
No harm was done, and it sounds like fun was had by all.
To end with, I'm curious about something:
How exactly is your Paladin PrC "Very powerful" (other than the See Invis)?