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.
If my memory serves me correctly, it is rather easy to decouple natural from player made blocks. It was either stored separately on storage or at worst you can deduce it by "subtracting" a fresh chunk generated from the seed.
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).
