I've got Ner'zhul by TKO
Knowing how nefarious and cunning Deathwing CAN be, if Arthas was still the Lich King when the Cataclysm occured, I'd predict a strong alliance between Twilight's Hammer and the Cult of the Damned. There'd be much stronger Scourge activity in the Eastern Kingdoms (and Kalimdor to a lesser extent) from Deathwing possibly discovering a way to funnel the undead into the territory of mortals (Portals a'la the original Horde's invasion?).
Another scenario I see playing out is a bid for power back and forth between the two. Deathwing would probably win just with raw power over Arthas if the two were to engage in direct combat.
Then bolvar would have a new chin as well as a new helm
One thing not mentioned in this thread is that Arthas would require more hit rating to not miss on Deathwing... he'd need about 20% hit rating, unless he's running with a boomkin... Deathwing would only need around 10-12%. Also, he'd have better gear an much more mastery!
Dw could therefore itemize for less hit and more crit thus increasing his potential dps on simcraft. And its Dw, he's pr0, he checks simcraft.