I'm slowly starting to form a Theory about an issue in the game, which may be obvious but I haven't seen it discussed.
The apparent symptom: People who play on higher difficulty seem to be the most vocal about how heroes dominate the game.
Ok, to break your theory I will become vocal about heroes dominance.
I have so far played only on normal difficulty and have used only heroes and pioneers in real games (ie not the first 3 aborted half hour games to learn it). I stoped making exploerers after the first game as they always died to monsters and never actualy explored anything, I stoped making troops as they were never anything like my heros, took forever and took away from building real stuff in cities. Heros could always do it better.
Even when I decide to end the game and kill the AIs it has always been with my super friends: The sov, whatever champs I have gotten and their associates - found monsters/troops, summons, my dog. Nothing built in a city by me, I really dont need cities but for some mana I guess, not even really the shop.
I was annoyed at the end of my last pre .98 game as the baddy AI had so many troops it took 3 or 4 turns to bust thru em all to get to the cities. 2 stacks dead a turn for atleast 3 turns, plus some leftovers on the next turn. Literally took no losses at all, all the supa friends survived, then went and took his empire, again no losess apart from an ice elemental, who was back straight away, as thouhg he had never died.
I now playing .98 at challenging, it doesnt seem any different. THe same strats are working just fine for me. Of course this may change as more playthru occur but nothing is screaming at me to change styles.
I dont think the problem is heros level or experience, the problem is the incredibly slow research. I do use troops when I get them free, I got a nice pancea (sp ???) archers once. They were quite good fire support for my heroes, I would build my own but I have never actually researched a bow in the game. It doesnt last long enough.
Similiarly when I see the 2nd size groups of troops it is much harder to kill them. I imagine having the next level would be alot harder again and company level or whatever its called with some magic kit or ranged attacks would be quite good at stopping my heros cold.
I have never got past the 2nd size group of troops (never built it either) and have never fought bigger then this from the AI. Again it takes way too long to get to.