Searching for sites multiple times ?

[Borg]

I got a little confused.
The manual states you don't have to search a province twice.
If a certain site is not there after one search it won't be there after a second search either.

So, I search a province with a N3E2 mage and I get nothing.

Later I search that province again with my new Lamia Queen D2N2 (desperately looking for my first Death gems) and she finds the "Den? of Verdant Greenery" which produces 1 nature gem/month.

Now why does a lvl 2 Nature mage finds that one while my lvl 3 mage earlier didn't ?