There would be a spawn, for naming purposes lets call her Nex. She would be a unique model of (insert pet family here). Once she would be tamed (or killed

Pros:
She would be a pet that a hunter really had to HUNT for. No camping, no spawn point circling. Only you, your mount, and a direction you had a hunch for.
Other ideas:
Her spawning location could determine her level: (Ie spawns in Deepholm, she would be level 82, spawns in Westfall she would be 13, etc)
She could spawn similarly on the same timeframe as the STV Arena chest. Perhaps at 3:00, 6:00, 9:00, and 12:00 server time she would spawn. This could possibly cause a fun "race" to find her in the wild.
Perhaps she would be like Kirix or Ghostcrawler (basically unkillable by any person) ~ Most hunters would be happy about this obviously

I posted this in the Lurker thread and felt that perhaps I'd throw a topic out there as well.