I've seen that happen in the past, when the underlying procedural generator was altered in some way. That was back in Alpha though, and you would indeed get sudden changes in terrain generation at the edges of the generated land. But that concerns the bottom layer of procedural generation, defining what is land, and what is air and water. Notch made a blog post about this particular step but hasn't gotten around to describing it any further. The next step is cave generation, and after that the grass, sand and stone is defined. Then all the plant life is planted. Those are the basics of any Minecraft world, and these generation steps have been present since pre-Alpha.
Notch hasn't made any significant changes to these since Beta, and how could he? Suddenly everyone would start complaining that all of their coolest seeds are different now. That's why all the new features are being added to the end of the queue. You can tell by the underground lakes because there's occasionally a tree floating above them.
If the same process is applied to villages, dungeons, and ruins, i.e. they also get added to the end of the queue, then the basic terrain layout isn't going to change. Anything that was a mountain wil still be a mountain. See the introduction of sandstone into the world, for example; the deserts still looked the same, the only thing that got changed is that the bottom layers of deserts and beaches were now made of sandstone instead of sand.
