They should come back possessed by the Burning Legion, leading the Legion's forces in an all out assault on Azeroth. They should have a semblance of their former selves left over, struggling with the possession. By the end of the expansion, we should have experienced their fall and possession (including how they continue to fight back), and be attempting to save them from the corruption while at the same time defending Azeroth (and we should lose many of the initial battles . . . would love it if our forces were initially overconfident). The tie in on the horde end is Sylvannas (gives Blizzard a way to stop making her a "muwhahaha" villain and give her depth back) and through alliance heroes on the ally side.
I'm sick of cardboard cutout villains. Give me another hero turned possessed villain who is still fighting somewhere inside (Arthas, Darth Vader, Kerrigan).