There are a great load of consequences: If I can think of more, I'll update this post again.
Without Arthas saving him, Ner'zhul would've continued to lose his control over the Scourge. We would have more and more Forsaken in the world, especially in Northrend. These northern Forsaken would be large part Vrykul, and would such form a new Empire throughout Icecrown and Storm Peaks, possibly based out of Jotunheim or Ymirheim. They would turn their attention to the true "death-god", Yogg-Saron.
The living Vrykul would eventually be forced to retreat to the east, basing their land out of Utgarde Keep. With two rival Vrykul empires - one living in the east, one undead in the west - Northrend is plunged into war. This is essentially what Terenas talks about after Arthas' death - without a Lich King to keep them in check, the undead will gain free will and set out to conquer the world.
Suddenly finding themselves in No Man's Land, the Drakkari tribe might find themselves in the same situation we see them now; insane, trying to fight the undead. As Drakuru doesn't have a Lich King to align himself with, Drak'Tharon Keep isn't completely overtaken by the Scourge, and thus retains some troll population. The Drakkari might align themselves with the Utgarde vrykul, forging an alliance between the two.
Without the Scourge resurrecting them, the Knights of the Ebon Blade never come to being, which means that the Scarlet Crusade will still exist in the glory they had pre-WOTLK. With their most prominent leaders being Dreadlords, this means that a foothold for the Burning Legion in Azeroth will be stable.
Without the Scourge, the Cult of the Damned will become an independent faction, with Kel'Thuzad as their obvious leader. As they are no longer in the servitude of Ner'zhul, I wouldn't put it past Kel'Thuzad to put old differences aside and enter an alliance with Sylvanas, extending the Forsaken lands into the Plaguelands as well. They will meet strong resistance from the Scarlet Crusade, and the city of Stratholme becomes a place for great war.
As Illidan did the bidding of Kil'Jaeden and succeeded, he would probably be rewarded in some way - or, more likely, killed off as his purpose is served. Without Ner'zhul to worry about, the Legion might've had a larger number of forces attacking the Dark Portal, allowing them to push through and take control of the Badlands. With these two combined, it would have changed the order of Azeroth greatly.
Personally I still find that whole "there must always be a lich king" bit from Teneras at the end of ICC was utter crap; simply kill the damned remaining things, to just go out and say "lol they'll wipe out Azeroth with no Lich King keeping them in check" to me both diminishes the LK's value as a credible evil boss (as well as Arthas being evil, that whole attempt at redemption thing was stupid) as well as saying there was still more untold numbers of phantom undead lying around; unless they're all going to start swimming across the ocean to mainland EK to join their brothers in the plaguelands, yeah right...not to mention it makes all the work we did killing fucking scourge throughout northrend seem pointless if there's still allegedly enough to wipe out life on azeroth and that a compassionate LK is holding them in check.
Otherwise, criticism of the actual game dialogue aside, I do like Umbra's synopsis, very likely the Legion would have been set up enough to mount yet another invasion of Azeroth, they could easily reopen the Dark Portal and without Illidan being a half distraction on Outland, likely they would have swarmed and defeated the remaining scattered Alliance/Horde settlements left on Outland for easy access to Azeroth. I'm also willing to bet the surviving nerubians allied with the proposed drakkari/living vrykul alliance, as they really don't like their turned brethren either, not to mention general immunity to the scourge except when killed and raised makes them good allies.
Some other outcomes I've randomly thought of; without the events of TBC taking place (largely since Illidan would not have fled to Outland had he killed Arthas), I'd venture a guess that the bulk of the remaining Belf population would have died off, having not many demons to siphon magic out of and no revitalized Sunwell at all to draw power out of, unless (according to the lame comic book characters anyways) they discovered on their own whoever the living fragment of the sunwell was and sacrificed her to reignite it. There would have been no Belf pallies either since they wouldn't have discovered the Naruu and sucked light out from it.
A lot if it also depends on how you write Illidan as well; would he have continued down the destructive path of serving the Burning Legion? He betrayed Sargeras himself in the revised WotA and helped seal off the Well of Eternity, and he always comes off as a flawed hero of sorts. Point is he's always scheming, so you never really know...he could easily next be trying to summon Kil'jaden through the Sunwell instead of Kael'thas in TBC, or he might have just as well went off into hiding to try escaping them, as he wouldn't have been driven mad with his defeat to Arthas. As for lady Vashaj, her purpose fulfilled she probably would've slithered back to Azshara and general naga scheming, might have seen them arise sooner instead of never.
What role the nerubians would play is debatable. Technically, without the Lich King to preside over them, they have no real reason to dwell in the surface world. They could easily withdraw into Azjol-Nerub once more, fighting Yogg-Saron and his minions down there in the depths. With the Scourge gone, they can focus entirely on Yogg's forces.
Remember that Illidan and his forces had already been to Outland before - including Kael'thas. He could have seen the potential that the Legion held, and joined their ranks immediately. He might have become the new lord of Outland, should Illidan have been promoted or executed, and by extension the main villain of TBC. (In a sense, he was, but I'm thinking box-cover villain.) TBC's story shows hints that the Legion wanted Illidan out of the way; Kael'thas supposedly engineered the attack on Shattrath, which weakened Illidan's position significantly by causing him to lose the Scryers.
There will still be a splinter faction within the blood elves; Kael's followers, and the former high elves that still remember The Well of Eternity that outright oppose the Legion. With Kael's position in Outland enforced, Silvermoon might fall to the Legion and become another foothold.
Technically, Illidan claimed that he wasn't defeated - which, depending on your definition of defeat, may or may not be true. He wasn't killed, that's for sure, but he certainly didn't do what he was supposed to.
Originally Posted by Ihnasir
Umbra - you are a god.
...I'm not really sure how to respond to that, but thank you. I'm just a lorenerd with a thing for What-Ifs, but I guess there needs to be a god for everything.
Things would have been really... really bad if Arthas lost.
Illidan would've managed to reach Ner'Zhul and destroy him, the rest of the Scourge would go rampage in Azeroth and eventually destroy all life. Illidan would've likely retreated to Outland, and gained a reward from Kil'Jaeden. Illidans armies would've been 10x bigger than his armies we've seen in TBC.
Also, Kael'Thas would still be allied with Illidan. Which means Outland will pretty much be impregnetable (did I spell this right?). Whcih also means that Vahs will create her second Well of Eternity and Kael'Thas draining unlimitless power out of Outland. Which also means they have more than enough power to destroy Azeroth.
So either the crazed uncontrolled Scourge or the huge armies of Illidan would've whiped out Azeroth