I think I remember seeing a game like this; moving along one axis also moved you through different periods of time, so that a wall that blocks your path "today" wasn't built "yesterday" and might be a ruin you can jump over "tomorrow".
It's not a maze game, but that sort of reminds me of Braid (platformer featured in Indie Game: The Movie) where you had to move back and forth through time to navigate certain obstacles. Very cool, and very beautifully rendered.
