So long as the players are delighted with their cleverness for solving your mystery, then you’re running a great game.
Let smart players feel smart
Have you ever read/watched a mystery story, and guessed the big mystery right at the outset? It’s not boring — it’s a rush really. You collect the additional clues that make you more sure of your hunch, feeling clever the whole time. Let your players have this feeling, if they earned it.
Definitely do not change the answer to your mystery if the players surmised it correctly.
Guessing the answer doesn’t mean knowing the answer
Don’t assume the mystery is over just because somebody guessed the outcome. And don’t let on when the players guess the mystery — let them wonder if they really are right.
Countless times, I’ve had players guess the answer to a mystery, then lose confidence in their hunch. Sometimes a player with a wrong idea but a stronger personality will lead the party back off track.
Red Herrings
You can toss a red herring or two at the party to make them doubt their conclusions. Misleading clues are a staple of mystery stories. It’s pretty easy to muddy the waters — an unreliable NPC witness, or an artifact that suggests involvement of an irrelevant faction can sow a lot of doubt. Just be careful not to get them too far off base.
Carefully gauge any increase in mystery difficulty
When the mystery is fully resolved, you might want to have an out-of-game chat with your players, to ask if they felt the mystery was easy, and if the next one should be harder. Don’t be surprised if they say no.
If your players do want harder mysteries, adjust the difficulty carefully. I think it’s way easier to make a totally baffling mystery that will just stump, confuse, annoy, and ultimately bore your party.
One technique is to provide early “leads” that have very little information, but provide a direction to investigate. Mysterious disappearances along a particular street of road is an example.
Read or watch more mysteries
If you haven’t done so already, make sure to read or watch mystery stories yourself. Pay particular attention to the early clues given in the stories.
If your players are into mystery stories themselves (and it sounds like they might be, based on their perceptive deductions) you might want to find out who their favorite authors are…and then read something else.