Ok, so on my last shard I maxed my Scout's exploration skill, plus he had some gear and I had some buildings. He was able to scout plains provinces in a few turns (20%+ per turn). The issue is, he doesn't discover many locations doing this. That seems wrong. Even if the event doesn't pop up, shouldn't he discover all the locations that should exist in that province? This skill seems counterproductive considering scouting to reveal the best locations faster seems like the point of enhancing this skill.

Am I missing something? Does he reveal all the locations and maybe just the provinces I explored had few?

Every site has a "% explored needed to be visible" value attached to it, and they're all already there (but hidden) after the map generation. So yes, the province you explored just had few sites in it.

Ok, phew. I was worried I was missing Knowledge stores or other critical sites.