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.