I don't have high hope for Message from Elrond.
If I take your exemple with sneak attack and test of will, either you play leadership/spirit too, or you are just putting dead cards in your deck, until you have Message from Elrond. If other don't play lore, Message from Elrond is a dead card too if you don't draw sneak attack/tes of will.
So the best use is with cards you can play and other can too.
Adding a hero that works with location being explored only make asfaloth and dunedain tracker more powerfull, and they already were... other means like new attachement or new ally are far worse and costly than these ones. Chance are, they will continue to make location asfaloth/tracker-proof and these new cards will never be powerfull enough.