I also want to conjure up [MENTION=3887]Mallus[/MENTION]! As a Cedric-sympathiser, presumably Mallus thinks that the paladin archetype can have cogency outside the romantic, providential framework that I describe.
Hello pem! Sorry for the delay, traffic in the virtual aether.
You've nailed the central problem with the paladin; they're idealized, romantic Christian knights from one literary tradition unceremoniously plunked down in another, into D&D's hodgepodge of influences, which include prominent elements of pulp swords-and-sorcery a la Howard, revisionist S&S a la Moorcock, and the amoral far-future picaresques of Vance.
So from the start, you've got the deck (of many things) stacked against the class; D&D's default implied setting strips them out of the moral universe in which they make sense. Worse, the game's original basic structure --kill or trick, loot, advance-- runs contrary to their high-flying ideals.
What's a DM to do? Either ban the class or cut them some slack.
(sorry if this is pedestrian, I'm not up to referencing Kant this morning

).
So, proceeding from the assumption the paladin class is only playable as a somewhat... compromised version of Galahad, what should we do about Cedric?
What I found the most amusing about this thread was the number of posters who admitted Cedric was an interesting character, but wouldn't allow him, presumably because maintaining a strict interpretation of the paladin class
in theory was more important that having an interesting PC active in their campaigns.
Interesting fictional characters (and their exploits) are
why I play/run RPGs. So PCs like Cedric are a godsend (pun intended!).
He's a cross between Patton and Martin Luther (with Luther's love of beer replaced by a love of hookers), dolled up in Galahad-drag. The story-telling potential there is considerable. Cedric represent an opportunity to insert a classic reformer's story into a campaign. It makes a nice addition to the dungeon-delving and monster-slaying. What DM worth their polyhedrals would pass that up?
There's an unfortunate tendency in the paladin discourse towards making the class less interesting in play, both thematically and ludically (is that even a word?).
For example, by forcing the paladin to, in a strict, literal sense, respect "all legitimate authority", you neatly remove the ability to tell a reformer's story. The paladin cannot oppose their unjust king, or their decadent church. To me, this is pointless, it robs the class of the kind of drama it's ideally suited for, as the paladin's authority is traditionally seen as coming from a divine, rather than temporal source, and shaking up the status quo is something they should be able, if not encouraged, to do.
In Cedric case, it's clear the legitimate authorities might be
wrong, and fun part is playing that out at the table, not predetermining it during the elevator-pitch phase of chargen.
And what id Cedric opposed his churches practice of selling salvation, instead of their sexual mores? I wonder if the opposition to him would have been so strong?
Switching gears... the idea that paladin's should follow the rigid strictures of tournament combat
while on the battlefield seems equally counter-productive. For starters, it's not how the class was originally conceived. AD&D paladin's were explicitly forbidden from using poison. But burning foes alive with Greek fire was a-okay. As were bows/crossbows. And, presumably pouring pots of boiling oil on enemies scaling the castle walls. And metal-clad knees to the groin...
Some gamers go so far as to equate smart tactics with dishonor. This doesn't make sense in a game derived from wargames, where smart tactics are a central component of play (it's also not very historical, so far as I can tell).
Giving players a script to follow, either in terms of their permitted interpretation of their PCs religion, or of their combat tactics (as Unearthed Arcana does explicitly for the cavalier and paladin) seem like the antithesis of good DM'ing. When I run a game, I'm interested in what the PCs do, not in what I'd do in their place.
And micromanaging PCs is not something I'd do for anyone, regardless of class. It does not lead to better gaming.
I kinda reject the notion that a DM needs to specifically define their setting's moral universe in order to make paladins playable. From a dramatic standpoint, that's the least interesting approach. If I were to run a game with Cedric, I'd leave the question, "is he a reformer or heretic (or both)?" to be resolved during the course of the campaign. Again, that's where the entertainment lies. Just getting players to color within my lines, so to speak, seems dreadfully boring.
Full disclosure: I know the OP, shilsen, so that obviously colors my opinion, but it also means I can dismiss the idea he's a disruptive player, or that Cedric represents a power-gamer's attempt to 'get something for free' from the paladin class (every gamer should be so lucky as to have a shilsen in their campaign).
Cedric's a thought experiment - is Cedric legal under the 3e RAW? Amusingly enough, despite my ongoing participation in this thread, that's the question I'm least interested in. It's the wrong question to ask. Unless adhering to rules-orthodoxy is the principle goal while gaming.
A final thought: D&D paladins are a lot like Jedi. Iconic fictional constructs whose moral systems don't bear scrutiny. It's best not to think too much about them...