Okay, this has happened twice now and I can't quite get the hang of how to address it; wandering a province and come across a structure (shop, temple, etc.) that needs my help (recover my tools from harpies/kill the necromancers/etc.) but the structure doesn't appear in the structures listed in the province (Troll Lair, Bandits, etc. but no Harpies/Necromancers).

Sooo....how do I complete these quests in these outlying provinces?

The Quests I got thus far where kill XX amount of Lizardmen.
I don't know why the people of the shards hate Lizardmen so much, but well.

I think you have to kill the appropriate number of specified enemies to advance the quest.
Or there should be an exclamation mark showing you where your relevant monsters are.

The question mark designates a province with the givers of a quest, not its target. There's no quest compass there :P

With kill XX, you just have to slaughter a specified number of creatures with this hero's army, wherever you meet them. You don't have to kill them with the hero personally, his units are good enough; other armies and non-hero troops (guards, garrisons) are not.

With recovering something, you have to "explore" the provinces and attack specified sites (such as "bandit lair") until you find a correct one. You can't know in advance where the site is and which among the similar sites contains what you need. Again, the quest is assigned to the hero in question only, other heroes probably won't find anything. The sought sites are typically not too far from questgivers, maybe one or two provinces away.