Um...dunno about puzzles per se but a session or two ago I had my players go on a sort of "scavenger hunt" using some riddles. A wizard gave them five cryptic clues about the items they were supposed to find in a tiny village he sent them to.
The items they were supposed to find were:
The skin of a hero (a suit of armor)
The blood of a scribe (ink)
The thoughts of a scholar (a book)
The comfort of the working man (a beer/ale)
The body of an innocent thief (the actual body of a magpie with a penchant for stealing bright shiny objects)
They had to figure out what the clue was talking about, then find the item, and place it into a magical bag. If it was the correct item, it would disappear when placed into the bag. If it was incorrect, then it would just sit there. The only restrictions were that the PC's could not buy, steal, or kill for the items.
It was a simply one-night adventure I ran b/c many of our players were missing on a particular night. Since we were short-handed and the party was still first level I wanted to run a combat-light session w/ an emphasis on problem solving, teamwork and roleplaying.
Hope this sparks an idea or two for you.