Moiraine's balefire seems to have been enough to destroy Bel'al before Shai'tan could intercede thus neither being partially over a gateway nor being partially in the Dreamworld are necessary factors to prevent transmigration.

My money is on the idea that the balefire was woven using so little Power that it only shaved a few seconds off of Asmodean's life, which means his soul may have been burned backwards and re-inserted into the reincarnation pool before it could be snatched by the Dark One in a coherent form.

Also it seems to me that a 'soul' is more or less a coherent entity - unlike a limb, which you can lose one of while being alive, I think a soul can't really be in 'two places at once' - the body might be, but the soul is still coherent. That is the whole idea behind a mindtrap - the victim's soul is in a physical vessel outside of their body, but they can still move, think and act independently.