Is the user’s feeling of being “clever” rewarding enough?
In older games, that would be enough for many users, but modern games have more complex rewarding mechanisms. There’s visual rewards (a beautiful looking cutscene), story rewards (what happens next?), the satisfaction of beating a hard challenge or spoils that let you become stronger, and much more.
Different rewards work for different users, not everyone enjoys games for the same reasons.
How do I find the right difficulty for puzzles?
First pick your target audience. Is your game made for a 5 year old discovering puzzles? A 50 year old puzzle master? Or somewhere in between? Then make a game that starts easy, so the user can learn how to navigate it, and that it gets harder and harder, requiring the user to take advantage of most of what the game has to offer to beat it.
Are there any mechanics that don’t work at all (in your experience)?
Whatever you do, you have to offer to users something new and unexpected. Other than that, different users like different mechanics, so it’s difficult to say what works and what doesn’t easily.
Everything I mentioned here is my personal opinion, I’m still learning myself how to make fun new game concepts, so feel free to form your own opinions based on what I wrote :)