The main question is what level of magic do we use.
We separate them to 3 very rough categories:
Low level: part of your toolbox, usually affecting one creature, used all the time
Medium level: rarer, A weak world enchantment, affecting a city or a a few units, used occasionally and affects the tide of battle
High level: a strong world enchantment, decides a battle
MoM has a wide variety of spells from all 3 levels, from a simple Haste spell to a Zombie Mastery spell. Many of the spells in MoM will fall into the Medium level
FE has a small variety of spells, mostly from the low level and the medium level. While you can cast Haste or Chain Lightening, I can't think of any "Oh god, he just cast that spell I really hate, now I gotta go disjunction that".
AoW3 has a lot of low level and a few high level spells, with a bit of a lack of medium level spells. This just mean that there is a shift between early game and end game. (note- some of the "spells" are passive bonuses, so they do not really enter this, though they would've been counted as medium, usually)
A tactic such as you described, raising a mountain ridge around a city, is not all that effective. It will mean starving your city in order to delay the enemy. Not only that, while you had to raise 9 mountains, all the enemy has to do is lower one (and yes, I'm assuming that if you made mountains impassable that wizards know how to deal with that).
As a reference to this tactic, MoM sorcery school has a spell, I think "city in the sky" or "sky fortress" or something similar, that prevents all ground troops from attacking the city. This could be countered either by disenchanting the city, or recruiting/summoning flying units. Another reminder- most races had a high tier flying unit.
The AI shouldn't have such a bad time, with the proper tools. Helping him work out certain tactics can be a problem (such as kiting), but on the other hand he is expected to be much more optimized. For example, if buyout cost on buildings is reduced at certain production points, the AI knows when to buy it so as to pay the least and get the building the fastest. The same goes for micromanagement- building an army in one city to defend another, the AI can send the units each turn to the right destination or wait and send them in a group, while for human players it can mean a hassle or that they forgot/made a mistake when sending troops.
In FE for example the AI has much easier tools to decide if -10% unrest, an outpost (to connect territories) or a +1 production/material will yield the most production. For me that tends to be a bit of a hassle, and I follow a per-determined order of buildings, even if it's not the correct choice.
All in all, I don't see why the AI is inherently inferior to players, or why high magic setting causes a problem for AI. Saying that the AI has a problem in AoW3 due to magic is like saying that the AI has a problem in civ5 because of the 1 unit/tile or some other reason for it in civ4.