One of my units was on the edge of enemy territory (with whom I was not at war). Between the end of my turn and the beginning of my next turn, the enemy influence expanded to cover my unit, and another tile between the unit and my border.

I was no longer able to move my unit anywhere, as that prompted the "do you wish to go to war with us" popup that you receive when you try to cross the influence border of an enemy you are not yet at war with.

The unit effectively was stuck in enemy territory. I could either leave it there, or disband it.

My suggestion is that when this occurs, and the player chooses the option not to go to war with the enemy - ie, "yes, we will not trespass" - then the offending unit, if already inside enemy influenced territory is teleported out of the influence, or to a friendly town.