They're horrible.
What game developers don't realize is that failure is a much more interesting way to develop characters than success. With all this focus on (minor) branching storylines in RPGs these days, I think it's pretty inevitable.
PLAYER! Meet LABYRINTH! Did you manage to get out of it as you were asked to? Great, here's an awesome reward! Don't get out of it as you were asked to? Character begins to panic, then panic even more... some bad stuff happens, maybe a tough boss fight, which culminates with you getting out. Less reward, or maybe same reward but had to beat a tough boss that doesn't give any of his own loot, and you get some nice dramatic scenes that you wouldn't have gotten otherwise.
As long as your character failing is part of the experience, it won't be frustrating. It'll feel like as essential a part of his journey as anything else he's done. If you're MEANT to succeed and the game pauses completely while you figure out how to do that, then yeah, that's last millennium game design. And that doesn't just apply to lost forests, it applies to just about all puzzles.