There’s a quest in the DH starting zone that allows you to sacrifice either yourself or an NPC. If you sacrifice yourself, you die, and as you corpse run, you get the following:
Lord Illidan Stormrage: Interesting. Like me, you have an immortal demon soul. You cannot truly die. Instead, your soul will make its way to the Twisting Neither. There you will wait until you can find a suitable body to inhabit.
Now get back to your corpse while there is still time and bring me the keystone!
So basically, Illidan has been corpse running since BC
