Reynard said:
I am not so concerned about whether the PCs, in their capabilities and (down the line) power levels, fit into the dark ages/medieval milieu as I am about the world in general.
I think the first step is deciding that the PCs -- and the foes who are on even footing with them -- are rare, unique even. Ditch the demographics rules right out. Get rid of "NPC classes" in general in fact. In a world where 99.99% of the people are "0 level" commoners, artisans and nobles, things can hew closer to what pre-modern Western Europe was like. If magic -- whether arcane or divine, whether in characters or monsters -- is rare, it both remains wonderous and does not impinge upon the historical versimilitude of the setting. If only one in a thousand or ten thousand can cast fireball or cure disease, the esitence of those powers will have no perceptible impact on society or history.
One of the big things, though, is monotheism. The influence of the Church on western Europe during the dark and middle ages cannot be overstated. More than magic or technology, leaving this out and following it to its logical conclusion would create a world far different than the one of the dark ages and medieval period. Now, i don't think it matters whether or not the priests and/or saints can actually cast spells or not, since people believed in the power of God and his servants in that time period with no real evidence anyway -- after all, people came from leagues away to gain the healing power and blessings of Benedict and if a fantasy setting counterpart could actually bestow those things, I don't think it would make the character any more powerful or influential than the real Benedict was.
As far as D&D rules not fitting the milieu goes, I think this is a clear case of "3rd edition rules, 1st edition feel". Slow advancement and deadly adventures can go a long way toward stripping the 3rd edition "super-heroes" of their capes. Eliminating the magic item economy has any number of beneficial effects, from mainting medieval feel to making the rare powerful monsters that much more frightening. Of course, it would be easier to do in 1E where many of the rules are already in place and, more importantly, many rules counter to the milieu are not in place and so much is in the hands of the DM, but I am more interested in doing it in 3E simply because it would be harder (and therefore more rewarding).
Of course, the goal isn't to have a "historical" game -- it is to have a fantasy game set in a plausible historically-inspired setting. these are two very different goals, I think.
Rarity isn't good enough. Imagine one party of moderately-leveled adventurers, acting in adventurer-meiter.
Party: (approaches small village on outskirts of fort)
Fighter: "Greetings, good folk! We seek refreshment for-"
Villager: "A woman! You've got a woman with you, in man's attire!"
Ranger: "Man's attire? I kill things with a bow and hide in underbrush! The attire is unisex."
Villager: "'Tis unnatural and we will have naught to do with such things in our village."
Wizard: "Oh. So, I should just wait outside then?"
Villager: "What?"
Wizard: "What with me being a wizard and all."
Villager: "Witch!"
Wizard: "Oh, no, sir, you are thinking of warlocks, whose magic is clearly flavored to be dark and-"
Villager: "Burn the witch! Heresy! Blasphemey! He will bring curses and plague down upon us!"
Fighter: "Good people, please, listen to us! Would you truly seek to slay this man simply because of his chosen profession?"
Villager mob: "Burn! Burn the-"
Fighter: "OK. That makes you lot evil."
Fighter: *Great Cleaves through mob on his surprise round, and spends his upcoming move action posing*
Ranger: "We kill evil things. And take their stuff."
Fleeing villagers: "The king will-"
Fighter: "This is the same king who tortures people, right?"
Wizard: "Will he send his armies? Please tell me he will. I'd hate to think I took Widen Spell for no reason at all!"
Villagers: "You can't defeat an entire army!"
Wizard: "Really? Who'd like to test that theory?"
Like I said, imagine one such party, making their way across the land every hundred years (or even more rarely). The mere concept of individuals capable of doing such things would shape the world. The problem is that there are certain pretty fundamental assumptions about the way the world works that support a medieval-esque world, and D&D 3.5 not only kills these assumptions but feeds them to barghests afterward. You think that the church has an impact on soceity? That wizard can Planar Bind celestials; I wouldn't imagine that too many religions could survive a concerted physical and spiritual attack from figures straight out of their mythos.
Slow advancement and deadly combat can retard the problem. But once you've got one pack of adventurers that make it to level eight or so, they are pretty much going to be walking setting mechanics, because by that point, characters are tough enough and have enough abilities to start engineering the environment.
Let us take a single hypothetical eighth-level druid. This druid, if she chooses, can remain shapeshifted into the form of a perfectly unremarkable wild animal indefinitely. The druid can (if she takes Natural Spell) bombard her foes with the fury of nature, raining down fire, lightning, and hail. The druid can slip into her foes' midst, than turn into a wild, furious beast. Worst of all, the druid can simply move about the land using Plant Growth and Diminish Plants to ensure that her enemies starve, and the larders of her allies are full to bursting. You know those horrible plagues that infested life in the middle ages? She can start them, as well as saving select individuals. This druid can bring back the dead, see her foes from afar in natural pools of water, and summon legions of horrible creatures to wreak havoc. The druid can follow ships under the water, then use her magic to drop the water around them, trapping them for over an hour while she takes whatever action she pleases (including casually sinking the boat.) If threatened, the druid can simply take the form of a bird and fly away.
And this is just one character. Imagine a party of similarly-powered individuals, all willing to use their talents in synchronicity. Either you posit that similar individuals exist to check them (and the world becomes not at all medieval), or the first moderately-leveled characters that decide to change the world do so unopposed.