I had a similar problem. I once created a world in 1.2, and in a extreme hill biome there was a dungeon that overlooked a river (then I looted it and such). Then I wanted to recreate the world (now this was post 1.4ish) to screenshot/film the dungeon only to find it not there. I also had a desert dungeon in 1.2 that wasn't there post-1.4. As for mineshafts I had one over a ravine of lava in 1.2. In the 1.4 world it wasn't there, and instead a mineshaft was in a deep hole leading down to the ravine. Don't know why the world generator was changed but it did irritate me.
So with mcedit I can delete the affected chunks-both the restored ones and the hole one-that sounds great, rebuilding not too much of an issue, but how will I know which chunks to delete?