Upon being denied entrance to the Old Camp, the Magicians of Fire are dead anyway, talk to Saturas and press on him for alternatives. He will explain that there was a forgotten thirteenth sorcerer who helped create the barrier, but he broke off contact from the other mages, now dabbles in necromancy and owns a tower somewhere in the Orc Lands.
First, if you were a member of the Old Camp you can now join the New Camp. Join the Magicians of Water if you were a Magician of Fire, or the Mercenaries if you were a Guard. To join the mercenaries, talk to Lee on the dam. He tells you his story and gives you the Mercenary's Armor (Weapons 55 Arrows 10 Fire 25) and can also sell you the Heavy Mercenary's Armor (Weapons 55 Arrows 10 Fire 25) for 2100 Ore. If you have the Ore, be sure to buy it. If you joined the Magicians of Water you get a free Water Robe (Weapons 65 Arrows 5 Fire 40 Magic 15). Again, 2100 Ore will get you a Heavy Robe of Water (Weapons 70 Arrows 10 Fire 45 Magic 20). Be sure to buy it.
Normally, I prefer a method of doing things as the challenge comes to you, so I will put this as a spoiler:
Before you leave the Old Camp, you should be prepared in more way than just expecting to be descended upon by packs of Orc Warriors and Fighters. Unless you're a mage, you should purchase Scrolls of Fire Bolts and Scrolls of Ice Bolts; if you ARE a mage, you should be sure that you can use Fire Bolts and Ice Bolts. Cronos should be of service, either way. Also, you should possess some kind of hammer weapon and for those you should talk to Sharky, or go and grab the infamous "free hammer" in the game.
It doesn't matter how you infiltrate the Orc territories. Technically, you had already done that twice, though the only time that should count now is the Ring of Stone and you passed over/skirted past a portion of the territories when you went to the mountain fort. The unofficial entrance to the territories next to the Old Camp results in no different treatment from the last time, unless you were kicked-out of the Old Camp and therefore are a "kill-on-sight" target. The path that Pacho warns you against leads directly through a considerably large pack of Biters and dumps you into the territory surrounded by Orc Fighters, Warriors, Scouts, and more Biters. From the Ring of Stone you can go back towards a group of look-out towers patrolled by Orc Fighters, Biters, and Razors (super-Snappers); going east from the Ring of Stone is equivalent to climbing over the rocks at any time on the path leading to the New Camp. To the west of the Orc territories is the Orc Camp, a quaint place where, if you approach haphazardly, you will be trampled upon by literally a hundred ornery Orcs.
If you enter the territory and head towards the south-east region, you should see a foreboding tower in the distance and it is there you should head. There are two ways to the tower - a jump onto a ledge where some Fire Lizards are waiting to the west, or a climb through a narrow mountain pass where golems or various kinds are waiting, to the east. There is an Stone Golem, an Ice Golem, and, around the bend, a Fire Golem, before you see the front door to Xardas' tower.
The first level of the tower is not very interesting, except for the chests and the Lesser Demon. Oh, and there is a Lesser Demon. As you approach the monster it will force-dialog you and, after you've learned that Little Timmy has fallen down the well, you can get the Demon to let it see its master once you've completed a "test of faith." The trial is cryptic but easily rephrased as: kill Golems, get hearts, give hearts. After you're done, you should give the hearts to the Lesser Demon and it will give you a teleport rune which will take you ... one level up. The chests in this room are yours to pick through. Climb another level, cross over into the other tower and you will find the thirteenth magician reading from a book to your left. I, for one, expected to fight Xardas. Or his Lesser Demon. Or him AND his Lesser Demon. Whatever.
Xardas talks with you about all that has transpired and tells you that the Magicians of Water's plan to detonate the ore mound to crash the barrier is not the solution. He tells you about The Banished Orc Shaman who is crucial to finding the Sleeper and/or solving the problem of the barrier's existence. I liked his point about how no one cared about the barrier spell malfunctioning but they either put emphasis either on living with it or breaking it.