I don't know if you'd count this as a 'puzzle', but I ran a campaign once where I tried to give the players themselves some extra challenges. For example, once I purchased a cheap, second hand lock-box at a flea market ... filled it with pennies that I'd painted gold and silver, plus a pair of "Very Fine" juice bottles that I labled "potion".
I told the players they could roll "pick locks" at any time, but if they could actually get the box open on their own I would give them an xp bonus (I forget how much). They worked on it for over an hour and never did get it open but had a blast with it. They still bring that story up from time to time ...