[thejeff]

I'm not sure what you mean?
When you first set a mage to monthly cast a site search spell you can look at his order and see the target. Next month, assuming you had gems left and more provinces to search he has a new target, which you can also check.

That target is picked sometime during the turn generation process. The simplest assumption is that it is picked immediately after the previous month's spell is cast. This seems to fit all the evidence and leads to the weird behavior described.
While playing your turn, you can see that the mage has orders to cast his spell on a province you no longer own. That you could no longer set him to target. And if you don't change it he'll go ahead and cast it.