I usually proceed in 2 steps :
- First I send "search squads" of 1-2 assorted mages (level 2+ in as much paths as possible) to search the most obvious magic-rich provinces
- Then I complete the searches with scrying spells, when I have a significant income, and now that we have a "repeating spell search" possible (even if not perfect).
There's a special case for Death and astral, as the spells only need 1 level, whereas manual search at level-1 is insufficient : here I use spells only if I don't have level 2+ mages (let's say I don't play an astral nation and find sage for example).
Usually, this way I'm pretty high in the gem income charts in MP, and waaaay above any AI in SP
