I remember years ago showing xscavenger to two kids of ages 10 and 11, and they had a lot of fun with it after some basic explanation of the (slightly wacked) hotkeys, for at least the first 5 or so levels, after which the puzzles get pretty feindish.
See also:
http://packages.debian.org/xscavenger---- http://bugs.debian.org/xscavenger