Parvateshwar: Yeah, I remember them from Warcraft 3 lore as well, so they aren't a new addition. I can't say much about them before that as I didn't read too extensively in the first two Warcrafts, they were a bit before my time. I would be interested if it does work in attracting new users, their membership has been stagnating as of late and if they can boost it above the 15 mil mark they might last a few years more, or at least until a competitor comes out (please GW2, don't disappoint me).
There were no pandaren, night elves, draenei, tauren or scourge in the first two Warcraft games, and the first game were
just Orcs and Humans (as the title suggested). The second game replaced Orc spearmen and Human crossbowmen (labelled archers) with Troll axethrowers and Elven bowmen (also labelled archers), and added goblins, gnomes, ogres, and dwarves as a couple units per team.
Unless I remember wrongly, Pandaren were originally meant to be an easter egg, or a joke, but it was well received in the team so they fleshed it out a bit more. Then the players started wondering about them, so they were eventually officially incorporated into the lore (with the development of Mists of Pandaria).