[Radek]

If you have the Vanish spell then you have a chance. Go to the shrine, turn right and check the "forest" there. At one location, you will see a strip of "sand" behind the forest. The sand belongs to the area behind the shrine and the Vanish spell can inject you through the forest there to the area behind the shrine.
Therefore, save the game and try. Perhaps, you will need several attemts to find the right place and the right direction of your party. But the success is granted in the end.
Without the Vanish spell, you have no chance. If it is the case, then send your moon magic caster solo to the wilderness so that he can gain a few levels quickly, improve his Mooncraft skill, and learn the Vanish spell.