Honestly, if you hate teleport so much, make rules in your games, personally remove the spell in your games, or something to that effect. But really, you are blowing everything out or proportion. Take a few things into account.
- Casters who can teleport go with the army. Thus, if I do send an army somewhere via teleport, then that champion is with them. Given that archery can turn any caster into a pincushion, it's a vast risk to teleport an army on top of an enemy.
- Teleport to defend cities? Same as above, but at the end of the day, you have the ability to shift troops via either one (just the Sovereign) or perhaps even champions with the power to do so. It is not an instance of gather-all-of-my-armies-and-use-them. If people DO teleport around the map, then they are losing the protection that the caster offers in terms of buffs, damage, and what have you - all because the mana to power, say, a lightning storm is being used on teleporting.
- Teleportation is indeed limited. Realize that if the enemy drops an army in on top of you, it won't be a constant thing that happens every turn. Once you take out one enemy army with the teleporting caster, it won't happen again unless another caster teleports in. Meanwhile, if you are victorious, the enemy is weakening their cities and losing valuable magic-wielding champions. It's not anywhere near as bad as what you are going on about time and again.
Now you like to reference Age of Wonders. I will, too. How so? Like this.
In the first Age of Wonders - the main game, pre Wizard's Throne - there were spells to teleport. City Portal, for one. The random teleport for another. The difference here is that a teleport in Elemental is an instant thing, for one. That is, if I use it, it's instant, the mana is gone, and I go from there. In Age of Wonders, I can 'store' a spell. Prepare it, and after a turn or two, cast it. The end result is that the spell is cast, and I can go anywhere, and then pop in with a full mana bar and all of my magic ready to unleash absolute hell.
Thus, a difference: in Age of Wonders, intelligent teleporting would not hinder me in any way and would, in fact, be a wonderful boon. In Elemental, if I just teleport armies all willy-nilly, it'll drain my mana (global, as of 1.1) and lay the smackdown on my effectiveness. Furthermore, teleporting an army in to counter another army isn't as steadfast in its power as in Age of Wonders. In AoW, a high-levelled army would more easily defeat even a slew of low-levelled armies. In Elemental, soldiers are much stronger (pet peeve of mine) and armies can square off and, regardless of size, one may win and another lose based solely on tactics. Units mattered far more in AoW individually than in Elemental.
As to replayability: keeping teleport in will do absolutely nothing. It's something you have to plan for, and is a strategic matter. The only person who is going to go off and believe that it is overpowered is the one who isn't prepared for it to happen to them. You have to understand that in a world of magic, magic is going to often blurr the lines of strategy and reality, as well as sometimes trumping them.
If someone decides to teleport to defend, then they lose an army somewhere else doing something else. That is, my exploration army can't explore when it's defending a city. My defensive army can't defend if I teleport it out to smite a city somewhere. It is a sacrifice to use, and it may be a boon to some degree when used properly. Like any other tool in our arsenal, we have to use it correctly in order to win.
The key? Learning how to counter it. That's part of the strategy. And if you can't learn how to counter it, then remove it from your game, or create a mod that does that, or enforce the rules of no teleportation. But I, for one, relish the challenge of taking this one double-edged sword and learning how to use it effectively, and how to counter it.
-Nathikal