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).
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.