Just as a quick summary, since the behavior is not obvious.
A mage casting a site search spell will default to the lowest numbered province that has not been searched (at all) in that path that has less than 2 known sites. If there is no such province he will stop monthly casting and if ordered to cast will target his current province by default.
Capitals are treated the same way as other provinces. I threw together a simple
mod that adds an empty site to each capital that only had one.