Anyone who has read Terry Pratchett's Men at Arms will know that paladins can bluff. Carrot Ironfoundersson, then a corporal with the City Watch (he was subsequently promoted to Captain) and one of the most paladin-like characters I know, needed to get into a guild to do some investigation, but was told by his superior to leave if he wasn't allowed in. When asked by the doorman (I am paraphrasing both the query and the response) what he would do if he didn't let him enter, his response was that he had been given specific instructions what to do if that happened, and he really did not want to follow them, but would do so very reluctantly if he had to. The doorman let him in because he sensed he was telling nothing but the truth.