This is great idea, but may be tricky as people often just mess around with the world. You would need to, somehow, decide which abandoned base is visually appealing and/or matches the environment.
Then you just need a good heuristic to guess whether or not a group of blocks matches your definition of a base to be explored.
You could take this a step further; once you have determined that a set of chunks have been modified significantly, you could apply that set of changes to the same coordinates of any map generated from that seed, meaning you can combine changes from multiple worlds into one (with the same seed).