We made it.
We eventually find a secret temple most likely to the God of Betrayal. We enter and the mage we rescue runs ahead, grabs a scroll, and init starts. Oh boy.
Big fight. Some lucky rolls and a couple of hard hits later, one dead mage, two fried rescuees, a disintergrated rescuee, and a stone rescuee. We find a river and use some spells to get the heck out.
We head towards the horse. The falcon tells us the mounts are surrounded by some of the army. 6 live fighters, 6 dead ones, and a happy bear (ranger's bear protected the horses). We sneak up, knock them out and tie them to each other, splash some ale on and take their pants.
All in all mission complete because the one person we were supposed to rescue to safe and sound and we take a week break. Wizard is happy considering we found the enemy wizard's spellbook.
If we didn't find a river, we would have most likely used the Ankheg idea. Thanks to all who posted.