@Jason: Your point is valid from a gameplay PoV, but from a lore perspective, they already begun establishing how all of these makes sense.

Night Elf Mages: In the Onyxia patch (3.2.2) PTR there's a quest on the Temple in Darnassus where a Highborne (yes, a Highborne, like those in Dire Maul) is seeking for an audience with Tyrande Whisperwind. While he's waiting, a temple guard harasses him and basically calls him "traitor scum". This opens interesting possibilities...

@Elmo: The lore for Tauren Paladins is currently in game. See that quest near the Dalaran Horde portals called "A Injured Colleague"? When you complete it, you can stay there and listen to a conversation between The Druid Tahu and the Warrior Aponi (A pony?). He talks about the imbalance in the Tauren belief system that basically imitates the Night Elven one, without taking the Sun (An'She) in consideration. Many speculated at that time that this would open the door for Tauren Palas and Priests. Now Blizzcon confirmed this.

I, for one, welcome our new Holy Cow overlords.

If I'm understanding correctly, the Taurens are looking at how balanced the Nightelves are which is why their beliefs shift to include the priests and paladins now, but NE don't have paladins... unless there's something I'm missing?

@Deadly. No, I think they're saying that Night elves are unbalanced. Nelfs only worship the moon, whereas Tauren worship the Earth Mother who encompasses the sun and moon as her eyes. So far it's only been expressed through the druids (moon worship) which is what the two NPCs are talking about.

Lore-wise the priests from different races use different means to heal. The spells are the same because of the necessity for the game mechanics, but they get their power from different sources. Nelfs use the moon, Forsaken use the 'forgotten Shadow', Trolls use the energy of the world via Loa spirits or voodoo magic.