But by the end of of IX, any pretense of a purely "medieval" setting was out the window. Hell, same with IV and V.
I'm not trying to troll here, but you really were so put off by VI-VIII because of the settings? I always found FFs VI-VIII to be the height of Square's creativity with the series (as far as world-building goes). Different strokes, I guess.
To answer the original question, originality is key. I love unique and strange settings, but a traditional "medieval" game world can be just as great when done well (hello there, DQVIII).