Yeah; unfortunately, due to the way the travel system and the combat system are structured, this is not at all easy to change.
The "right way" to fix it, in my view, would be to make the game understand a bit more about how you are traveling—for instance, that you arrived in the city from the region to the south, so that's the only region you can leave through unless you've managed to win a battle or there was no opposition. Or you successfully evaded.
For now, this remains as a game-balance necessity, but fixing it the way I outlined has long been one of my intentions for the game.
