Re: 7N+D after your first searching - that's partially just the vagaries of the RNG. Sometimes you get really screwed. I've searched 20 provinces as Caelum, and come up with an Air income of 5 (including the 3 from my capital, it was awful!). Ironically, I did quite well in that game after becoming quite pessimistic. Your options will certainly be limited if you come up short on your preferred gem types, but it doesn't have to be the end of the world - though it may be the end of a strategy, and the beginning of a new one.
Acashic record is actually hideously inefficient now, with remote searches fixed. You are still much less effective when you search the provinces that already got 2-3 sites, but searching per path (may cost more mage turns, sure) costs you 15 gems and 2 slaves to hit everything, except any provinces that hits 4 will stop searching, and you can just cancel out searches on a path once the easy pickings are done, if need be.
Indie mages can do wonders for you. No nation should -ever- have to go without Nature searches, due to the proliferation of indie N mages. Search enough provinces, and the majority of my games find me Enchantresses. Their random paths are unreliable, but over time they will give you access to all 4 elements. Likewise, there are numerous other sites that give nice multi path mages, that will unlock doors for you.
Manual searching has only one purpose - unlocking a baseline gem income of any path which you have no income, but you have mages available. Now that remote searches are fixed, you lose nothing but a little mage time to go out and do these searches. Only have an S2 to start manual searches? No problem, your spells will hit those provinces again later, if you choose to allow them to.
I still do a lot of things wrong in this game, but I am quite positive that Mage Turn + 2 Gems = Worth It.
The more searching, the merrier. You would be amazed what you find, if you just put in the effort to search everything. Sure, sometimes you don't get as much of something as you want - but if you milk your income of everything else, it makes trading or substituting into effective options.