I know it's a myth, but what would stop the Minotaur from just going full Juggernaut and smashing through all the walls should the Minotaur realize the paths are too difficult to traverse?
Imposter Syndrome
I thought about this as well, after my first remark. I think this issue could be solved by building a secondary labyrinth of ventilation ducts to channel the fresh air into the dead ends, in a way that entices the Minotaur in very confusing ways. The ducts could even have baffles that open and close, just like real ventilation systems in houses with zone-control airflow.
The ventilation ducts could also work to confuse and terrify any humans who were sent into the labyrinth. They’d carry sounds allowing the human to hear the heavy breathing and bellowing of the Minotaur in ways that make it sound like he’s always just around the corner!
The more interesting case is that Sisyphus can contemplate the nature of the system, and reason toward an out that involved undermining Hades power over the Underworld. If he could pause and do experiments, discover the limits of the enchantment, and work around them, that would be ideal. However such an option would also be an excellent way for Hades to extend and deepen the severity of the punishment. A god's arbitrary power is arbitrarily powerful, after all.
Perhaps what all those Greek epics taught me, is that once someone condemns you to a destiny, then that’s it. No other destiny can open up.