2 Cents
I always thought it was important to keep in mind that some of the restrictions of a Paladin's code where due to his alignment, some were due to his religion, and some were actually due to his (economic) class. A Paladin is essentially a noble (or a wannabe noble) who believes he is better than the commoners around him. Now that sounds like arrogance, but it also involves a commitment of sorts, and a Paladin is someone who takes seriously the prospect that his behavior should reflect his superiority. This is one reason why (at least in first edition with facing) I always maintained that he wouldn't strike from behind (unless an opponent was too cowardly to face him while beating on someone else). This is why he won't lie, etc. It's not just to be good and serve the deity, but to establish his honor, and to provide a basis for distinguishing himself from those around him. It's his way of explaining the difference between himself and his servants. He had a code of honor, and in following it, he distinguished himself as a character of truly noble character. It is an attempt to make his status as a noble mean just that, that he really is noble.
I also think some of the penalties that accrue from these behavioral restrictions can be compensated by rewards for loyal and honorable behavior. In my campaigns, Paladins who skirt the rules may keep their abilities, but that's it. Those that stick to their codes on conduct are rewarded (with information, magical aid, and even of course, the prospect of a Holy Avenger) by their gods. Of course the gods don't show up personally, at least not until very high levels, but they have their minions and messengers.
Some players honestly can't seem to grasp the significance of a Paladin's code. They look at it as a hindrance, and they sek to minimize its importance to their play. The better players recognize that it is the source of their abilities, and the price of those abilities.
On a side note, I never did like the rule that a Paladin could not associate with Neutral or Evil characters. I could see that if there were no other values at stake, but I never ran the meet-in-a-bar-go-for-a-random-adventure campaign anyway. If a Paladin and a character of low honor had common cause, I saw no reason the Paladin could not work with him. The Paladin must not, however, use overtly dishonorable tactics such as planning a sneak attack, etc.
I've also never bought into the kill-evil-on-site motif. Social Manicheanism is close to what defines evil in the real world as it is often enough the source of suffering. If good slays evil on site, then it is no different really, and all we have are 2 different camps, each of which can be called upon to treat each other exactly the same way. That's an amoral universe, not one in which any moral outlook has any real meaning.