In another case, in order to depict Thrall visiting his ancestral home in Nagrand, he appears when triggered by quest turn-in while his Ogrimmar version never despawns, thus allowing all the newbies running Ragefire Chasm or the occasional person after Rend's head for old time's sake to continue their work -- and making sure that it's clear that Ogrimmar still has a Warchief. Then there's good old Griftah, who changed places 3 or 4 times over the course of BC. Finally, most people who played Alliance to level 60 before Burning Crusade came out know that Onyxia is technically in a couple places at once as well. In this case, Blizzard was willing to move NPCs around without "replacement" or make them appear in multiple places at once to give the feeling of a progressive storyline. It's simply understood that, lore and story wise, the NPC in question is only in one place, the place they officially are being dependent on where you are in a given storyline.
In the meantime, you may recall that Alex recently told us the story of Brann Bronzebeard, a Dwarven explorer who's been to every corner of Azeroth imaginable, and few unimaginable. Apparently, he's heading to Northrend next, and there's a good chance he'll finally appear as an NPC for the first time in Thor Modan. This has some people -- notably many of the commentors on Alex's article -- concerned that he'll be too static. A hearty explorer like Brann, stuck at the entrance to Thor Modan, permanently exploring one place? Seems a bit sad, some say. Of course, there's multiple ways Blizzard could deal with this. Certainly, he could go off exploring again at any given time and leave behind an assistant who will give out his quests like Rokaro, or he could simply appear in various corners of Northrend during any given patch like Griftah. Still, we've never seen Brann in game so far either, so maybe he's really decided to "settle down" at Thor Modan -- or his big brother Magni ordered him to stay there until he had answers about Dwarven ancestry, either way.
For me, I'm more of a fan of the multiple places ideal, where you accept that an NPC can appear in multiple areas at once, with the player accepting they they've "moved" for the sake of the storyline, but I think there's a place for the other methods as well. It's certainly understandable that Rexxar would move to his ancestral homeland, and Thrall could have another operative who could take over his missions, or that Hemet Nesingwary might have multiple hunting camps set up all over, traveling to and from them as the mood struck him.
When it comes time to move along the story, how do you prefer the NPCs be treated? Should they be replaced like Rexxar, or should they be "cloned" like Onyxia or Thrall?