The only way I can rationalise this is that whenever someone becomes a demon it destroys all other alternate versions of them in every other reality and then that 1 remaining demonic version can traverse all realities by crossing through the twisting nether. HOWEVER, does Gul'Dan debunk this, I don't know what proportion demon he is.