All righty, here's a brief history lesson, by yours truly.
First of all, let's discuss the validity of High Elven paladins, and where they fit in, and which faction the High Elves belong to.
The High Elves were actually a splinter of the Night Elves, and were separated by many thousands of years. They're all the same race, just different cultures. Several thousand years ago, according to the story, the Night Elves were actually the magical, obsessive, and very proud tribe of Elves (this is before the Alliance, and probably even humans, existed). The High Elves are the “Light” part of the tribe, and believed in holy powers. They were also very humble, and still are today. Just four years ago the High Elves were a very strong member of the Alliance, just like the Dwarves. The Alliance used the High Elve's highly disciplined form of “Light” for the armies' war efforts against the Orcs, before the Legion invaded. They used High Elven priests, and later on they started using their Spell Breakers (which are races that could debuff an enemy, and give the buff they stole to an Alliance member). In fact, the High Elves were the only source of primary healers, so I think we owe them thanks for being a part of our team. We might even thank them for the paladin class, since the paladin is so obviously based off of the priest, even though it is a Human and Dwarven variation of it. So, High Elven paladins make perfect sense, even though Uther Lightbringer, a human, was the very first paladin in Azerothian history.
So, if the High Elves were originally a very strong member of the Alliance, why are they Horde? The High Elves have a very strong hunger for magic, like the old elves. They want to be able to use the energies of the Well of Eternity, which was, and is, a fountain of magic and energy, and is what all of our magical abilities are based on. The Alliance didn't like such an obsession with the magic, and they have reasons not to, and so they treated the High Elves with contempt, and the High Elves hated them for it. Eventually, a few members of the High Elves, including their leader, Cael, were captured and imprisoned by Human forces. An opportunity came up for them to escape, and so they took it. After a long series and string of events, the High Elves were introduced to the Horde. Other than their obsession, the High Elves aren't particularly bad. They were just looking for a way out, and they decided to side with the Horde, simply because we, the Alliance, were becoming their enemy. They become the Blood Elves.
Ideally, there should be a third faction involved. The Orcs, Trolls, and Taurens forming an alliance makes sense, but the Undead and High Elves being allied to them is a little sketchy. Maybe in the future, Blizzard will let the High Elves and Forsaken split from the Horde, and form their own faction. There are just so many tribes and factions in the game, it's kind of confusing. Even Illidan is constantly brewing something, and he never seems to have the same friends from one game to the next.
I have to head into work, but I'll post the idea of Draenei shaman later on, if you like.