The Ban’dinoriel is not that invincible. The Horde was able to break down one of the Runestones during the Second War, as per Chronicle: Volume II:
Thousands of years ago, after the War of the Ancients, Quel’Thalas had erected a powerful magical barrier around its kingdom. This was Ban’dinoriel, “the Gatekeeper.” The shield was tied to a series of monolithic Runestones, relics that prevented the Burning Legion and other outsiders from detecting the arcane magics wielded by the high elves. They also weakened the powers of their enemies, such as the Amani trolls.
Gul’dan claimed that dismantling one of the Runestones would disrupt the barrier and restore the Horde’s use of magic. Then he and his followers would use the relic to strengthen the Horde for the siege of Quel’Thalas.
After much consideration, Doomhammer agreed to the plans. He didn’t trust Gul’dan. But thus far, the warlock had proved himself useful and loyal to the Horde. Orgrim’s spies in the Stormreaver clan reported no mischievous activities. What Doomhammer didn’t know was that Gul’dan had won these spies to his side with threats, promises of power, and other means.
Doomhammer still suspected a day would come when Gul’dan would try to betray him and take control of the Horde. He never could have imagined the truth: the warlock was planning to abandon the Horde.
In recent months, Gul’dan had nearly amassed the power to do so. Though the death knights had not proved to be as loyal to him as he had once hoped, he had the backing of two mighty clans: the Stormreavers and the Twilight’s Hammer. Yet that was not enough. Not nearly. The warlock needed as much power as he could get to fend off Doomhammer and any other foes he would meet on his journey to the Tomb of Sargeras. Quel’Thalas’s mysterious relics would give Gul’dan the strength he needed.
He and his followers quickly dismantled one of Quel’Thalas’s Runestones. They chiseled away at the monolithic relic to build structures known as the Altars of Storms. Gul’dan then turned to an ancient ritual used by the Highmaul ogres. In the distant past, they’d found a way to empower members of their own race. By channeling raw arcane magic into regular ogres, the Highmaul could transform them into highly intelligent two-headed ogre magi.
Few living ogres knew of this technique, but Cho’gall was one of them. He handpicked the brutish ogres who would undergo the transformation, and he oversaw the rituals himself.
Before long, two-headed ogre magi emerged from the altars. They were just as powerful as Gul’dan had hoped they’d be. More importantly, they secretly swore their loyalty to him.
Now, all that remained for Gul’dan was finding the right time to make his move.
With the Runestone desecrated, the Horde’s death knights and other spellcasters regained their powers. Orgrim’s forces stormed toward Quel’Thalas’s capital, Silvermoon City. They terrorized the countryside, pillaging settlements and cutting down every elf they found.
King Anasterian called on his greatest generals to stop the Horde’s advance. Elf magi and rangers spread across Quel’Thalas to resist Orgrim’s forces, but they did not have to fight alone for long. Turalyon and Alleria soon arrived with half of the Alliance army.
While Turalyon organized his soldiers and launched attacks against the Horde, Alleria met with Anasterian in Silvermoon City. She urged the elf king to pledge his forces to the Alliance, but he needed little convincing. Anasterian was furious about the Horde’s assault. Not since the ancient Troll Wars had the elves died in such numbers. Not since that terrible time had their lands been so defiled. Humans and elves had once banded together to save their respective kingdoms from oblivion. Now, they would do so again.
The Alliance would have the full support and backing of Quel’Thalas.