Random walk? Other battle wierdness...

[Cohen]

Probably the Baphomet has teleported himself into the province.
Magic Movement (teleport, cloud trapeze, gateway, and such) is the first movement.
After, if after the magic move there're battles, those are solved.
Then there's normal movement.

So on the Baphomet come alone, a triggered the first battle.
Probably he lost, so the province was still held by enemy.
Next in normal movement phase the Prophet and his army get into the province, triggering a 2nd battle.