Paladin should have been a PrC from the get go in 3.0 in my opinion, they went to the trouble of making the blackguard the antithesis to paladin a PrC so Paladin should have been the same way.
In my campaigns Paladin is not an allowed class, there are 'mystic' knightly PrC's and for each deity there are tailored paladin-like 'divine champion' PrC's. So abilities are not always the same, and it allows for paladins outside the Lawful Good framework. A player has to state their working towards that for their char or I'll determine through their characters action during game session if they might qualify for one of the 'divine champion' paladin PrC's, in either case theres quests and other things they have to do in game to get the PrC, be it wanting to enter one of the mystic knightly orders or their gods choosing them as a champion. So far we have taken existing knight/paladin PrC's and adjusted them to incorporate features of the paladin class when a player is interested in a specific one, and if its as a 'divine champion' we tend to go over it as a group and determine the PrC's abilities so everyone is happy about the play balance, but even then we are mostly just adjusting one of the cleric/divine type PrC's with some Paladin type abilities that would fit for a specific deity. So not all 'paladins' in our three playgroups have lay on hands for example. Well out of 17 players theres only 3 paladin-like characters right now, 2 are what I call mystic knights and one is a divine champion and everyone is happy with the adjustments we made tot he PrC's we adapted.
I'll admit that this approach might not work in all campaigns, but so far everyone seems happy with the compromise.