TLR - in current state of wow undead paladins are unlikely. With a tiny bit of lore twisting/creating - they would make more sense than sunwalkers.
I love the "Dark Paladin" or "Shadow Paladin" idea. Saying the UD Pally uses Shadow magic the same way the UD Priest does to heal. Lore would be explained that they are not using the Light, and Gameplay mechanics would stay intact with the understanding that melee and spells are shadow, not Light.