[ Spoiler ]
Since it's already a contrived idea to begin with, you might as well run with it.
Claim the walls are made out of a strong, highly processed material like Hardened Material (Barrier Rating 32, Object Resistance 10+). Give it some kind of reactive armor so that if it receives any blunt trauma, such as a Smashing Blow, it reacts in kind. Maybe it sends a powerful electrical charge back at the attack/attacker causing stun damage like a really powerful stun baton, or maybe it does physical damage that's enough to hurt a metahuman target but not the wall itself. Whatever, it is, bashing through should not only prove futile but hazardous to one's health.
Next, coat these walls with high-Force Guardian Vines. If the mage/magicians go astral or just astrally perceive, the vines will be able to attack. And at a sufficiently high Force (Force 12 or so), the mage won't stand much of a chance in taking it on. Assorted high-Force Masking Wards and bound Elementals along the way will insure that any foci the characters have will need to be deactivated, or they will have to go really slow as the mage tries to synchronize hsi way through each one. The Elementals will basically just be the strong men to help in case the magician finds a way to take on the Guardian Vines.
After that, give the place a really high Background Count (or make it an Aspected Power Site that's attuned to the style of magic practiced by whoever created the maze/the mages that helped construct it; simultaneously giving them a bonus while the players get a penalty if magic comes up). Now, even if the magician does manage to get around the previous obstacles, he's still temporarily crippled.
Flood the maze with FAB Strain II so that a projecting mage can't move very fast. FAB III should be avoided since they would feast on the Guardian Vines and because it takes a long time for it to affect a mage anyway.
Finally, place the maze underground. Even if the mage is able to project, once he gets past the walls he'll discover that he has to move really slowly (base time of 30 minutes per meter) to get anywhere, and even if he does, he'll never be able to see the entire maze to figure out the way to the exit.
All together, that should at least help keep the mages and Smashing Blow adept busy and maybe force them to come up with some new ideas and tactics along the way. It's all really contrived, but then again, so is the maze to begin with.