Yes, a slowed creature can still escape
There is a relatively obscure rule hiding in the Player's Handbook - Start/Complete Full-round Action
The "start full-round action" standard action lets you start undertaking a full-round action, which you can complete in the following round by using another standard action. You can’t use this action to start or complete a full attack, charge, run, or withdraw.
So a slowed creature can use a standard action this round, and a standard action next round, instead of the full-round action necessary to escape the maze.
Yes, a slowed creature can wait out slow inside the maze
Creatures explicitly get their turns inside the maze:
Each round on its turn, it may attempt a DC 20 Intelligence check to escape the labyrinth as a full-round action...a plane shift spell allows it to exit to whatever plane is designated in that spell
This text would make no sense if time was not passing for these creatures (because then they could not take actions). No mention is made of the maze plane being timeless, either. So the victim's spell effects are ticking down, whether the slow debuff, or any buffs (such as the fox's cunning the creature might cast upon itself to give it better odds of succeeding on the INT check to escape).