Your willingness to accept "flavor" seems to have a direct relation to replacement crunch
Well, I don't understand how that comes accross, but here's my position on the fluff/crunch issue:
Fluff is great. It adds dimension and deapth and turns the game into something better than just a wargame. It's not essential by any means to play a fun game, but I definately want it in my games.
Fluff should define the crunch that follows. However, fluff that is not supported by crunch is wonky. If you have a long history of orcish theater, but orcs, by the mechanics, suck at theater, I'm going to wonder: how did orcs get this when it's just not enjoyable for people in the setting to watch, including the orcs?
If the dwarves in your land are the greatest sorcerers around, that's great. But if there's no mechanics supporting that, no way for a PC or NPC to actually *be* a dwarven great sorcerer, it's something that's frustrating.
The Core Rules contain enough crunch to support a lot of very diverse flavor. If I want to play a warrior of honor and nobility, they give me a way to do it. Same thing if I want to play a blessed future king, or a mounted knight who follows a code, or the reincarnation of the national hero or someone who holds himself to a higher standard than a mercenary or a warrior beholden to the temple or 1,001 other character ideas, I have a class in the core rules to support that. And that's without really changing the flavor at all. If I change the flavor, even a smidge, I can support other things. Make the code one of Chaos and Evil, and you can have a defender of wickedness rather than an attacker. Say that the land grants these powers to those who rule it, and I have an enchanted noble. Describe them as following a stringent code of
Bushido and I've got a samurai. Say that people are born into families with this class, and I've got Ksatrya. Describe their abilities as reliant on wearing the flayed skins of their enemies, and I've got something vastly different. Change the fluff to represent powers gained by meditation on the mysteries of the universe, and I've got a philosopher-warrior.
Now, that's all without changing any mechanics whatsoever. This is the first kind of alteration, the kind that most commonly happens on a character-by-character basis, or by a DM who doesn't want to muck much with the system to get what he wants out of it. Say I'm running this mesoamerican campaign setting. Paladins wouldn't usually fit there, right? They're knights in shining armor! But if a player comes to me and says "I've been thinking, the Paladin gets a lot of healing and defensive abilities -- can I change it to be a national defender of the Temple of the Sun, and wear the flayed skins of my enemies?", and my campaign can take the addition of something like that, I say "sure, why not. Don't expect many others to follow you, but you're a PC, you're an exception to the rule anyway, go for it. Most other defenders of the Temple of the Sun are not like that, and they don't wear the flayed skins of their enemies, but go for it. The God of the City has spoken to you specifically. Don't you feel special, ya weirdo?" Just by changing flavor, and not affecting the mechanics at all, I can get something vastly different out of the Paladin than the usual flavor would indicate. This is purely a change in fluff, and it's the lowest level of 'cooperation' that can be considered. I could have entire organizations of these 'flayed paladins' if I wanted, they could populate the world. And, if my world didn't have a place for knight-in-shining-armor types, but did have a place for this, it's a flavor change to something that already exists, that is still supporting it.
So while it would seem that dismissing Paladins in a Mesoamerican campaign would be sensible at first, but when you're willing to change the flavor to suit, it's not nessecary to ban the class at all. You just change it.
I could do that to a lot of classes, most of 'em, in fact. Just by changing the flavor text, I could have a "western archetype" fit quite comfortably into a decidedly atypical landscape, without doing much to it. If I'm going to advertise my game as "Mesoamerican D&D," or if I just want to accomodate a broader base of players, it's a very easy thing to do that doesn't ruin the setting and provides an outlet for those who like the phat powerz of the paladin.
I think that, if you don't want to re-design a class to fit, just think about changing the flavor to a different archetype that the mechanics still support. All the powers of a paladin can very effectively support a Flaying Templar. Suspend the alignment thing (flavor), hinge the powers instead on defence of the city (flavor), and say the powers are extentions of the Temple's energy itself (flavor), and perhaps hinge spellcasting on wearing the skins of the evil that threatens the temple (flavor), and you don't have to remove the "paladin class." It just changes the "noble, moral warrior" to fit a setting without Chivalry. Only if the class's abilities themselves aren't effective, or if the change overlaps something else, or if the class's 'role' is filled by something else should the class really be dropped. If I had a different "Flaying Templar" class, I don't need to change the paladin, and can either change the flavor to something else, or decide the niche of 'holy warrior with a code' is summarily filled and I don't need the Paladin's abilties, since there are other mechanics that support that flavor.
I originally thought that Dark Sun could've very easily done the same thing -- changed the paladin to fit the setting, rather than ditching it. It just so happens that in the process of changing the paladin to fit the setting (making the powers psionic instead of divine, mostly) it hits PsyWar territory, and, since a psywar can devote himself to a 'noble cause' related to an element as it is (perhaps even being a Psywar/Cleric), there's no real reason to keep the Paladin around.
Similarly, I thought DS could've done the same thing with the Sorcerer. But it doesn't matter, since the Sorcerer and the PSion have very similar *mechanics*, and the players of a Sorc would feel overshadowed by the Psion or the Wizard. Since a Sorc brings nothing 'exclusive' to the table, there's no reason to keep it.
On another note, Monks fit in the DS setting, flavor-wise, very well. It makes sense that unarmed combat would jump into a setting of fragile weapons and low tech. But because their mechanics would make them more potent in a world without powerful enough weapons, it's important to nix them for mechanics reasons. Their niche -- the unarmed warrior -- is served instead by Barbarians with high Strength, for instance.