Limiting the range (or scalling cost to range) would be anouther option for nerfing teleport to more manageable levels. I don't find myself using it very often anyway,usually the return spell is enough for me- and is usually used to shorten travel time for my exploring sov.
You are perfectly right to be frustrated with movement! When I criticize teleport I understand how people may go "oh god he wants me to spend another 100 turns going back and forth!!"
But that is not the point, because what I am trying to convey is that movement itself is wrong in this game. In Age of Wonders Shadow Magic, things are balanced, units's speed is just right not to make you mad about the slowness of the game. Cavalry can get you around a medium size kingdom in just a few turns, just to cover from quick attacks, while heavy infantry becomes a necessity only when dealing with strong units. Boats and flying machines also have a critical use in that game when teleport is not used.
If AOW had a system as good and complex as that of EWOM to develop technologies (ports, flying machines), I would still spend days and resources developing them because they would be useful in AOW! With teleport, instead, they become just useless.
In AOW things are well balanced: mounted troops (and flying units) are necessary to explore (horses should be available very early in the game!!!), infantry is used to conquest and defend newly conquered cities that would otherwise rebel. Wizards are used to freeze a lake and have units cross it, make units stronger or give some support in combat. Of course ther are also stronger spells to defend one's coutry (only effective artound wizard towers), there are healers that travel with troops and fix their hit points, units that are faster or invisible in woods... there are tons of tactics that are not even contemplated in EWOM (partially because they become REALLY fun only in multiplayer)... in EWOM, instead, turns go by the dozen before anything happens.... and I completely understand that people gets frustrated when they realize they have to move a unit all the way back by foot!
But instant travelling is just a cheap solution! A lazy, simplistic solution for the developers that can only accelerate a boring game. It makes parts of the game useless (building ports, having horses, roads, a complex terrain...), it kills strategic options and doesn't add anything to the fun. It only makes the game end sooner, and do I agree that, at that point, ending the game is a pleasant thing.
They should just check how movement works in AOW and start from there!