I dont think exploration was all that important in that game. Exploration is always of major importance but this game ended to fast for exploration to be of any use and I think this was due to your incredible recruiting power.
Also, you mentionned that their was a shack with a gluton guarding it and was surprised that we had not gotten rid of it. Well, you probably know it was near my ally and that I was to far away from it to go and dispose of the guards. Also their is almost no mines near my ally to use. I think he had only one maybe two. So by the time he could pump up the troops to clear it you had allready showned yourself in the caves and it was then too late to risk loosing troops to maybe recruit some interresting units. He had to intercept your troops or risk loosing what he had gained by your raidings.
Also, if you look a the underground level, you will notice that my ally had access to a lot of power nodes but the defenders where also very difficult to overcome, and if you add to that that nodes defend themself with spells, they where almost useless to him as he could not conquer them.
I was more lucky than him because a structure point allowed me to create my special dark elven structure to create succubus. This allowed me to create them and start charming me an army like you guys did, but at the difference that they cost me 150gp instead of 50, and took me 3 turns to build instead of 2. Although they did help me recruit the hugh stack that Maya destroyed, they did so at a pace much slower than yours.
Again, exploration is a major aspect of every game, and we did a lot of it (almost a third of the surface was explored and more than half of the undeground), we where lacking in troops in wich to use to explore (because it is either explore or clear shacks and stuff). Also, since my ally was of weak military strength, when Avlee (at the time being of Powerfull military strength) made contact in the southern parts of the caves (by turn 10 to 15 I beleive?) it was clear I had to help him, or face a 2 vs 1 match. So my troops where going back and forth and all other aspects (exploring, clearing shacks, etc) where of lower priority. So it was difficult to do anything.
Also, what really killed me in the end, was that the map allowed Maya to hoard some troops 0 days off my capital in a way that I could could only face him in this way: 1 of my stack VS 2 of his. Even if I had attacked him with 8 of my level 3 units I would have been destroyed. This small tunnel should have been edited out in my opinion.
Oh, and by the way, if you guys would be interrested in playing this map again (exactly as is with no edits) but with roles reversed, I would be happy to do so Anyway, congratulations again for your victory