Today, I ran over the web site of Boston Dynamics that features a video with a fascinating robot of theirs, the RHex ("The Rugged Robot that Devours Rough Terrain").
It's a six-legged machine that is able to walk over almost any terrain found out there, to climb stairways, steep slopes and railroad tracks and even to swim!
Though it's not a NXT robot, the video decidedly is some kind of inspiration in that regard (however, don't try to throw your brick into a pool of mud, don't you! Mind, it's not as sealed as RHEx...).
Watch the video - it's intriguing!