You say you want a reason for setting-specific restrictions (which DS has), but, in DS' case at least, you don't appear to really mean it.
I want a *good* reason. I don't think I've heard many good arguments in favor of these restrictions.
And having a character that is a warrior of honor is not necessarily the same as having a character that is a paladin. The D&D paladin class is a concept tied to a specific type of setting (psuedo-european/medieval worlds where divine forces of good exist), which is why it gets removed from settings where such a concept does not fit. Even in 3E (see Oriential Adventures for one example).
Both this and OA got a bit too tied up in the flavor text, methinks. The flavor text can be completely changed. I could write up the pladadin as a dispicable warrior of evil just by changing the flavor text. The mechanics for the Paladin class are not tied to any specificy setting, and arguably not even tied to a specific force.
True, horse riding knights of chivalry and courtly behaviour don't have a place on Athas...but the Paladin is much more than just that.
Bah, you're looking at it backwards:
Well, I'm looking at it from a player's perspective. As a player, if a DM is going to take the tested core rules and alter parts of it that I am interested in playing, I'm going to want a justification for that. After that, I can either alter my choice based on the world, or help the DM give a bit so I can still play the concept I want. If they're just going to give me some condescending "'cuz I'm the DM, that's why!" I'd rather not deal with someone who's that heavy-handed when I just want to play a game and have some fun. If they give me some off-the-wall "Horrible balance, I have no idea what WotC was thinking, they must've been smoking crack when they let halflings be rangers!," I'd rather not deal with someone who, as a DM, has that narrow a concept of their world. If they give me their rationale, I can give them mine, and we can work to form a common ground in which I can play the character I want, and the DM's world is still preserving it's flavor.
For instance, my most recent campaign was set after the world began, so there was no wizardly magic -- the secrets had not been discovered yet, so there were no spellbooks, no spells to speak of. Say someone wanted to play a wizard. She'd be totally within her rights to ask me to defend my choice as DM. I'd tell her: primitive world, no spellbooks yet. She'd tell me: I wanna play some sort of demonologist, I wanna use rituals to summon demons. I'd tell her: Okay, start out as a cleric-sage. Use summon monster spells, stuff like that. I'll work in the secrets of magic into the campaign, and then I'll let you trade in your levels of cleric-sage for levels of Summonner. Izzat cool? She'd tell me: Yeah, but I don't want to wear heavy armor or turn undead or anything. I'd tell her: Here, use the cloistered cleric. Here, try the philosopher class. Trade out turning undead for rebuking outsiders. Nix the heavy armor; you can just have, say, your Int bonus to AC like a Monk does their Wisdom.
Now, a published setting doesn't have that negotiating luxury, but it's pretty easy to think through, at least for many of the major ideas. At the very least, when they change something (which they should), they should give you the reason they're changing .
Take the "no gnomes" rule.
Bad answer: "They're extinct." (So what? What's the reason for them not being there?)
Good answer: "The world is technologically savage, and severe. There's little room for pranks or professors. Mischief is not tolerated, and there's no method for gnomish ingenuity to manifest. If you're interested in playing a prankster, perhaps a gladiator who wins by winning over the crowd and embarassing his opponent (without physically hurting him) would appeal to you. If you're interested in playing an inventor, perhaps a designer of gladiator weapons, or perhaps a city-employed engineer for wells or city streets, would be interesting for you."
Take the "no paladins" rule.
Bad answer: "There are no gods to power their holy might." (which is not even reading the original rules right.

)
Good answer: "The world is one of compromised morality, where in order to survive, average people must commit some horrible acts on occasion. If you'd like to play a hero with honor, try a psychic warrior, and focusing on healing and restorative powers. If you'd like to play a mounted knight, look at the riding lizards. If you wish to further enhance the idea, try becoming a cleric of a 'benevolent' element, such as rain, or a druid as a multiclass option. Consider joining organizations X, Y, and Z, which focus on fighting the good fight, and remember that organization Y may lead you to access to the Tribal Warden PrC."
See where I'm going with this? Don't make you restrictions absolute and involatile, and provide ways to play the same character archetypes in a way that is square with the world, and you won't end up peeving off players who just want to play a bloody fatalistic hero in a blasted world for a little fun on the weekend.