How I think this works is:
Mage 1 casts teleport from province A to B
Mage 2 casts teleport from B to A (due to randomness, after Mage 1)
<all other spells are resolved>
The game checks if any battles need to happen.
So, no they'll never catch each other because the fighting happens after all spells are resolved.