Lore changes and evolves. Look at the history of Warcraft Lore. Things change. There was once no Night Elves and no High Elves. There were also no Blood Elves. The lore evolved as time went on.
Of all the races to become paladins on the Horde side the Taurens make the most sense to me. Look at Tauren culture. Tauren history. In fact even more so than the humans, the Tauren are a peace loving people. Why wouldn't the righteous and virtous merits of the Light be attractive to some in a peace loving society?
Now that is a scary thought...8-foot tall cow man with clad armor and the abilty to heal himself is very scary,thanks for the post so we can stay on one thread instead of 30 of them =)