It is possible to balance teleportation and have the AI properly take advantage of it. HOMM5 had teleportation, and it was balanced quite well.
I liked HOMMV and yes there were teleporters, but I only liked the campaign where everything has been planned by a level designer and not by the random map generator, also it's single player and I would have probably hated to see someone pop in my empire without me being able to stop him or destroy the damn gate!
Can't speak for Sword of the Stars, I tried it but I can't get to like it, for some reason I don't have enough the feeling of an empire in that game: has to do with lack of city development and a general sense of a very (VERY) basic sense of management.
I know tha most people consider Elemental a single player game, but I still hope there will be a multiplayer option, especially by email as I already stated somwhere else. Age of Wonders is still alive because of customization and multiplayer after all, and that's should definitely be a model for this game (even more than MOM if I can dare say so...)