I just completed this and had read through the other Mission 5 walkthroughs. Thank you thank you for the awesome posts that were definitely a huge help to me.
It seems apparently there are various ways of completing this mission, but it presents many logistical problems. So here is yet another recount of a completed mission - including two errors I made which could be avoided.
1) FIRST GARRISON: Raelag takes all the troops and conquers first garrison, no problem.
2) TENT KEYS: Raelag goes south to take the blue tent key, and north where there is a sanctuary to get the red key. Here is a mistake: the blue key is not necessary to win this mission. Shadya can pick up gold and sulfur that's available, as there are three forthcoming Dungeon Outposts with one dragon per week, if you want to use them.
3) GOING UNDERGROUND: Raelag AND Shadya go underground at this point. Take the nothernmost gate/staircase, near the sanctuary.
The underground here is shaped like a C. Your initial position is going to be at the top of the curve. If you go around the C to the lowest curve point, there will be a monolith that will take you to the northwest parts of the underground. All of that is unecessary to win.
Go to the very center of the C. To the left, if you want it, is your first Dungeon Military Post with one dragon a week.
Go to the south of the C. There is a road there that heads west. On that road is another dragon outpost. Follow the road all the way west. There's a blue hero standing there.
4) ATTACK IDLE BLUE HERO (ALASTOR): He might have a different name, but he will be an idle inferno hero. Raelag attacks and defeats him.
5) GOING ABOVEGROUND: The inferno hero you just attacked was blocking an entryway to a passage south. With him out of the way, take Raelag south. There is your third dragon outpost. (All these dragon outposts give Shadya something to do, but this is your last chance to give whatever she has accumulated to Raelag.) Then you will see the stairway/gate leading aboveground.
6) SECOND GARRISON/JOURNEY WEST: You will come up by a hill fort. (Want to upgrade dragons? Got cash?) At left, take the garrison, not difficult.
Head west along a dirt road, past a gold mine. Enjoin the main road slightly north. Keep heading west. Watch your timing with GRAWL. If you time it right, you will avoid him altogether. If you can't avoid him, go back to an earlier save before coming up.
7) THIRD GARRISON: That's right, do not bother with the Inferno town. Just go west to the garrison on the far southwest corner. Mission objective, right? One key thing, Shadya has to go through this garrison as well. Take the garrison, again, not a hard one. Then see that Shadya safely traverses the road and have her go through where Raelag is waiting.
8) MISSION ACCOMPLISHED - Remember your battle was always with Veyer, not with Grawl.
NOTES: Looks like without the 1.1 patch you can get the spell Instant Travel or some such spell, the new Dimension Door. The scenario is very different then. What I've described above is with the 1.1 patch installed.
The towns are not worth taking, and are unecessary to mission
STATS:
RAELAG: Level 28. 16A, 12D, 32SP, 21K. Enlightenment, Intelligence, Scholar, Empowered Spells, Expert Destructive, Boots of the Swift Journey.
14 Black Dragons
7 Shadow Dragons
52 Deep Hydras
26 Matriarchs
47 Min. Guards
342 Assassins.
Battles: Poision with Assassins. Empowered Meteor Showers on cluster groups. (BTW, activate the grid for better view of this spell.) Empowered Implosion for single units. Emp. Chain Lightning for strings of four. Dragon and Hydras wipe out whatever makes it to your side of the battlefield, where they lay in wait. Matriarchs using slow or attacking outright.