Paladins in AD&D and OD&D need to have extraordinary high Charisma and this can be a potent weapon in its own right.
In this post on the theRPGSite Cranewings talks about a situation his players were involved in. Basically the Paladin was born in a conquered land and his religion has been taken over the conquerors own religion. He came across a girl that has information that could benefit the remaining faithful. But had the misfortune of running into an Imperial Bounty Hunter looking for the girl.
The encounter wasn't resolved well by his players, and so he posted his story. The replies had some good suggestions but they all missed probably what is the most devastating weapon that Paladin had, his Charisma.
If I was in that situation I would basically just talk pleasantries with the bounty hunter until the sun went down. With my high Charisma I could make the conversation interesting and be able to utter distract the bounty hunter until she had to leave. The paladin wouldn't have to lie, just artfully shift the conversation if the topic comes up. The bounty hunters leaves with the memory of pleasant conversation and none the wiser.
Now roleplaying games being what they are, situations change all the time. So how effective a Paladin's charisma will be greatly depend on the circumstances. But I think it will be more useful more times than not.
My 50% Hardcover Purchases at Lulu
7 minutes ago