On Clues
First an essential rule on clues: If you have a group of player characters in a sprawling mansion searching for some evidence of who killed Mr. Mansion Owner don't ever assume or ask players to describe each and every area that they search for clues in. This is a bad idea for multiple reasons. Pen and paper rpgs take place in our heads and only through explicit social agreement of location description do we share vaguely related images of the same imaginary places. Chances are you didn't describe the sprawling mansion so well that the players even imagine what you are, and so checking a specific place in the mansion that they're not picturing is out of the question. If you have described the mansion out fully, drawn a blueprint, et cetera don't assume these details will help. Say the mansion has 40 rooms (I have no idea how many rooms mansions have - I live in a studio) and it is only in the fourth parlor that the vital clue is in. Chances are players will just want to make a basic roll like "I investigate the mansion" or "I investigate the floor." For the love of speeding past redundant rolls just let them. Don't make them search through every single room unless each room has its own unique flavor, something interesting to discover, or something fun. If you make your players go through every room until they get to that one with the vital clue, they will never make it. They will disengage entirely by the time you get them there. By then they won't give a damn about the vital clue or who killed Mr. Mansion Owner (Answer: It was Mr. Wants-to-Own-a-Mansion).
On Inferences
Hinted at in the above is that it is not the clues that are interesting, but the inferences that players make with them once they have them. If you are of this opinion then I recommend making the acquisition of clues comparatively easy to the inferences that players must make with them. Scavenger hunting for clues doesn't lend itself to rpgs because it would essentially come down to a player saying, "I look in the dresser. Anything in the dresser?" GM: "No". "The refrigerator?" "GM "ahhh... sure, but it's not really important." Player: "oh..."
Inference, however, creates a logical puzzle for gamers to solve. Mr. Mansion Owner's corpse is found in his cellar, drained of blood. A half burnt circle is on the priceless rug in the library, and the maid says it was not there this morning. The study is filled with hundreds of lunar moths that are foreign to the region. Right away the mystery lover in me wants to know how these are related (or if any of them are red herrings). None of these would be hard to discover (or require a roll). The real challenge comes down not to the characters, but the players to find the connections. Which leads us to the next section:
But My Character Would Know!
If a player isn't great at logic puzzles but they're playing a character who is, or at least better than themselves, then to allow them to enjoy what their character is supposed to be good at let them roll, and if they succeed give them a hint. I believe that advice was in the DM guide for 4e. I thought it was a good compromise.
They Have All The Clues, Why Don't They Know Who The Murderer Is?
The players have seen Mr. Mansion Owner's corpse in the basement drained of blood. They've seen the half burnt circle, and the lunar moths. Shouldn't they instantly jump to the conclusion that Mr. Wants-to-Own-a-Mansion drained the blood to fool the player characters into thinking the local vampire killed Mr. Mansion Owner instead of Mr. Wants-to-Own-a-Mansion who used some obscure spell from a supplement text your players probably didn't read that involves burning half a circle into the victim's home, and the ritual, for some trivial reason, summons Lunar moths?
Don't make assumptions about what out of game knowledge your players have OR do have (but won't remember).
Don't rely on information from a gaming book and not share this information with your players if you want them to use it.
Do use complex and odd clues to be inferred, but don't assume what you believe to be the inference to the best solution will necessarily be the same that they come to. Chances are when you thought up your mystery you thought of the ending first, or thought of a good hook, came up with the conclusion and filled in the middle details. What I'm getting at is that you didn't have to solve your mystery and so you can't objectively assess if the inferences required of the players both validly and easily warrant your conclusion.
Also, if player characters infer that they ought to go to Night Club X to talk to Drunk Y, but you thought they'd for sure go to Park B to talk to Homeless Park Guy C either tell them that the nightclub is irrelevant or better yet just turn Homeless Park Guy C into Drunk Y. It'll save time, trust me.
One last thing on mysteries in general: Use common tropes like red herrings sparingly. They get old and predictable if used too often. Do use them on occasion. Just make sure to change up what tropes you're using: red herrings, player characters waking up with amnesia, et cetera (I don't want to give a comprehensive list because players I game with read this blog).