[Jack Simth]

It's not free teleportation - it's fee teleportation (or at least, it is with my suggestion). Some fee per unit (counting the commander as a unit) - perhaps 1/2 gold per size per unit - would deal with it - that brigade of 50 machaka spiders, led by a spider (size 6, weren't they?) is going to cost (51 * 6 * 1/2) = 153 gold (plus other expenses - the announcement fee and maintenence times some factor) - if you assume there is some amount of a magic economy hiding in the game (somebody is training those mages most nations hire, after all), it isn't unreasonable to assume that there is a teleportation section of the mercenaries' guild that is willing to teleport your units around for a fee when you hire them out as mercs - it would explain the default merc's ability to do so, and be somewhat thematic.

For living nations, a movement fee of 1/2 per size (similar to supply) is likely to be negligable compared to the maintenence over the designated time frame - 50 cost-10 archers cost 50 gold to move, but (10 * 1/15 * 7 * 50) = 233.33333333333 gold to maintain for 7 turns (and 500 to replace). For SG or AE Ermor, with no maintenence costs but little in the way of revenue, that same 50 gold transportation is expensive, even without the maintenence - and is moving nothing but cheap cannon fodder. Yeah, it could make alliances much stronger - but it isn't free teleportation - just gem free teleportation.