magic scale and keys
If you want a really hard puzzle you can try this:
You have twelve identical keys (or gems, or whatever it is you need to open the whatever to release the whatever). They are all very magical, and only one of them will work. Using the wrong key has some nasty side effect.
All of the keys weigh exactly the same except for the real key which weighs a fraction different than the others, a very small fraction, and you don't know if it is more or less.
You are given a magic balance. You can only use the balance 3 times, and you can only weigh keys against each other. Any other balance the characters try to "rig" won't work, either because of arbitrary magic in the keys, or because the difference in weight is so small that only a special magical scale is accurate enough.
Anyway, the puzzle is to determine which of the 12 keys is a different weight only using 3 weighings.
I used this in an adventure, they almost got it on their own. I ended up giving hints as time went on, lowering the amount of experience I was going to award for solving it with every hint.
How many hints you give should depend on how much you want them to solve it. You could write up a time hint sheet ... after 5 minutes the 1st hint, etc. Or whatever. It's a tough puzzle though.