@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.