This is somewhat related to the idea of a permanent medieval stasis that has "descended" on a lot of classical fantasy worlds. Of course, being one of the elements of medieval fantasy, it would seem counterintuitive to create a world that wasn't suspended in it. After all, one of the reasons we play games like Dungeons and Dragons, Castles and Crusaders, and Tunnels and Trolls is because we want dungeons, dragons, castles, crusaders, tunnels, and trolls. To remove or hamper the medieval aspect of medieval fantasy is to take it completely out of its element.
SO we have a profoundly ahistorical goal of preserving a certain type of world to play in. How can we reconcile that with the constant change that history displays? I'm certain some would say that it doesn't matter, that the topic should be dropped as either having no solution or being immaterial. But for me and for the people I play with, that non-answer isn't enough.
Historicizing, periodizing, and elaborating on the fantastic medieval can lead us down a fruitful path. Firstly, knowing that constant change and permutation are the hallmarks of a historical world (stasis and sameness being the hallmarks of an ahistorical one) we can immediately set out to give some dynamism to a fantasy setting by periodizing it. By establishing rough periods in the past where things weren't the same as they are now, we are already breaking the ahistorical model. Not to say that no books or settings do this, but some do not. If everything is cloaks and castles all the way back to the beginning of recorded time, we are presented with an unattractive ahistorical model that will reasonably illicit irritation in those interacting with it (the caveat, of course, "unless that's what they were looking for," is eternally present throughout this argument).
The first question we have to examine is one about the composition of the paradigm itself. The elements that we identify as being critical to the medieval paradigm are mostly stylistic and technological. Castles, tunics, hosen, horses, knights, fidelity, and the underlying social structure that leads to inequality and a military class are all important. Those things changed in our actual history, into a Victorian leisured nobility where romance and free time became the defining characteristics of a society of civil service. How can we preserve those elements and still call ourselves historical?
One of the biggest things we can do is halt the progress of science. I think I've already discussed how magic inhibits scientific thought (theoretically, of course) due to the way it "cheats." The analysis of the world would be conducted under a mystical/Art umbrella rather than a logical/scientific one. Magic breaks the rules, so manipulating the environment according to the rules becomes less important.
With technology mostly confined to stasis, we can safely move on to surface styles. If surface style and social structure are the only things that change (within a confined set of boundaries) we can effectively preserve the fantastic middle ages through any permutation. Fashion needn't advance to pants, it can remain within the realm of non-bifurcated garments (tunics!) forever. Just because our history introduced the suit there's no reason to think a fantastic history wouldn't develop variants of tunics, cloaks, &etc that look much more like their medieval predecessors.
Of course, the farther we get from a standard medieval groundpoint the more fantastic the setting becomes. But isn't that the point of fantasy, after all?
PS. After thinking about it for a while, I realized that I tend to actually try to draw on a completely divergent milieux: one that mingles the standard medieval fantasy with a sort of classical revival of paganism and classical non-Christian values descended not from the medieval church but rather straight from ancient Greece, Egypt, and Rome.