Everyone has been saying that villages, strongholds, mine shafts, and the new biomes may spawn in your current seed if you have unexplored areas in your map. When you throw out your map, the whole thing becomes unexplored. Will simply making a New map allow for these new things to spawn?
The only way to have unexplored areas of your map, is if no one has ever set foot there.
^This^ It's not what's on your map, it's what chunks have been actually generated in your world save file.
Yes. It counts. The system would have generated that chunk and saved it to the file when that person first explored it.