On the puzzles and riddles front, I don't think I've done much with it. I'm aware I the GM enjoy that sort of thing much more than my players, and unless you enjoy it, its gratuitous.
I do occasionally dabble with prophesies, and when I run mystery stories I don't usually allow for a roll to solve the mystery. I see these as story elements, and I try to use them on players I know will enjoy them. I'm also not adverse to players making skill rolls in order to get interpretations, suggestions for leads, and so forth.
Things I try to remember:
- It needs to be fun for the players. I have been given extra power as the GM and its important that I not abuse it. This is not my time to show off how clever I am.
- The game shouldn't demand that the mystery or prophecy be solved by the players. The bad guy should fold like a house of cards if my players get it, and they shouldn't be stone-walled if they don't.
- The prophecy or mystery should interact with the game. Possible answers should arise and be eliminated as they gather more information, and it should serve to focus their actions rather than to distract them.