Scout a province for a quest means that you have to send a scout to a province and wait till he (she) comes back. Then the province encounters are accessible. To be more precise, you only have to wait for the return of the scout. In high chapters that can take seveal days, so you have to time it well.
Afaik, there's no difference between solve and complete, both mean that you have to do all 8 encounters in a province (negotiate or fight) and get a rune.