Am I the only one that's tempted to point out the differences between a labyrinth and a maze? In a labyrinth, the whole point is simple to make you walk the entire length of the area, while mazes are meant for getting lost in.
And please note. That if you are going to tell me, "Yeah, but it's not that, it's this." Please show sources that conflict with what I've said. Really. The flurry of comments that are all like, "I know better, you're doing it wrong." And no one seems to understand that this is why I'm so sporadically on this site anymore. Relax. Breathe. And cite your source, because:
I do hope we won't be having the maze=labyrinth discussion. Because, really. The difference between them is exactly why you have maze puzzles, and not labyrinth puzzles.
Having said that, I would be exceedingly careful with those rules in mazes. Again, in a labyrinth, you only have forwards and back on a twisting and turning path. You have no choices.
Let's be clear here. This is a labyrinth:
(notice one entrance, one possible path, and one goal.)
And this is a maze:
(notice multiple paths, even if this is a simplified version)
Now that we're on the same page with this (and please don't try to dictionary.com me, because I'm talking about historical and mathematical fact). Is there a conceivable way that touching an outer wall will lead you to getting lost?
Let's start with known algorithms. In the link, it describes ways your wall-follower rule don't always work.
If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.
This means there are ways to foil your premise, and known ways. And that's in a 2-D maze. How much more so will this be the case if you add levels to a single maze? All I would have to do is design the maze so that all the outer walls are disconnected from the goal, and do that three or four times, and you'll be stuck in there for eternity.
Additionally. If you want to follow the 'left-hand rule'. Use it to get out of this maze.
(above is a simple maze)
And more importantly, perhaps for me, what's the purpose of this maze. I mean, if it's just for the sake of getting people lost, then I can imagine there'd be a host of other obstacles to overcome. Think in the terms of a dungeon-crawl for ideas how to make it considerably more complex.