Why does it need to instantly teleport? What about simply causing your unit to select a path outside your territory and only move that direction (as in you can't change it)? It would give more of a penalty to crossing someone's territory without permission because it would take you time to get out of there.
Teleporting as it is now is a bit, strange as well as unexpected.
