I've played that you can get rid of locations like this with the Northern Tracker. Is this correct? The card doesn't say that it's immune to card effects, but maybe I never notice a revision. I just figured it would let you heal him earlier without having to destroy the healing source.

Yep, you can certainly get rid of Rhosgobel without traveling to it. In fact, some successful strategies in that particular scenario are centered around using Northern Tracker and other similar effects to explore Rhosgobel prior to Stage 2 of the quest, thereby allowing allowing players to heal Wilyador more effectively (something you picked up on).

It's perfectly legal.

Thanks man. That definitely cuts some of the luck factor out.