I use the "teleport to mine feature" all of the time. If I send a peon to make a building and upon completion the peon is stuck in an enclosed space, I try to find an unfilled mine to send them to. It may be that the path-finding isn't very good at telling the difference between stuck and not-stuck, and that's causing the teleport feature to kick in when it doesn't need to. (This teleport feature also works when combining wisps to ancient wisps -- it has saved me many stuck builder wisps and lots of crystal/time. Via selection order and movement commands it's even possible to ensure the newly created ancient wisp ends up free rather than stuck.)
Path-finding may be the most poorly coded part of this game -- it causes all kinds of crashes if you make a custom map and don't make the available paths wide enough. Too many armies + narrow paths = major path-finding problems. Actually, that may be why you get the teleport sometimes and not others -- I would not be surprised if the game has some kind of global path-finding budget and when it goes over budget some units don't get any of that path-finding budget and the game treats that the same as the unit being stuck -- no path found. (I see very large enemy armies get stuck all the time -- probably because the few units in front trying to navigate a narrowish path weren't getting any of the path-finding budget, so no one behind them could move either.) That would mean you may or may not get a teleport depending on what one or more of your enemies that you can't even see is doing.
If there is such a path-finding budget, and it's just one constant somewhere in the program, it would be really nice if we could hack that number to be a bit bigger to take advantage of modern CPU power and make the units a bit less stupid.
Vendayn: A reset of the game (exiting the game completely, and opening WBC3 again) temporarily fixes it...but it comes back, randomly.
That is consistent with path-finding being the problem. When large enemy armies get stuck, saving/reloading frequently unsticks that army (probably by changing which units are getting to the path-finding trough first).