miguel said he thinks the detective genre is the best suited for adventure games. I wonder about that.
If we're thinking about the classic "whodunit" mysteries (police procedurals and other, more psychological/sociological sub-genres are a bit different), I think the big hook is the surprising revelation of the killer (or whatever type of criminal is being chased); that moment of insight when you suddenly see everything differently. It isn't (always) quite a twist ending, but it has a lot of the same appeal. This stuff is like crack for our brains, it's the same principle psychologists invoke to explain why we find jokes funny.
The flipside is that if you see the revelation coming, the experience is kind of underwhelming. That's not to say that you should never be able to guess the solution (it wouldn't be an interesting challenge if you have no chance of seeing through the author's misdirection; it'd just become an arbitrary flip-a-coin-to-pick-the-killer moment), but if you do it should also come in a flash of insight, not as the long-foreseen outcome of a steadily building pile of evidence. And once you know, the story is essentially over; it's just a matter of wrapping up all the loose ends as efficiently as possible.
That works in books and film because of the separation between the detective and the audience. In a classic mystery, where a genius detective cracks the case, we never have access to the sleuth's thoughts about the investigation, because then the reveal wouldn't come as a surprise.
But if you're playing an adventure game where you are
the detective, you'll generally work out the solution at the same pace as the character (and when either of you falls behind, the effect is usually frustrating). So either the whole case has to rest on a single "a-ha!" clue (which is hard to engineer and may make the rest of the game seem pointless), or you'll work it out gradually and not get that sweet, sweet eureka moment.
What I think is the real secret to the success of the Phoenix Wright games isn't the clever game mechanic, the comedy or any of that. It's that the cases have a pretty deep structure, with several twists to be unraveled, each one (mostly) non-obvious enough to give you one of those revelatory jolts when the pieces fall into place. Gemini Rue, the Blackwell games, and I - would guess - most other successful detective mystery adventures do this to some extent as well.
So to sum up a long post: adventure game mysteries have to be structured a bit differently than in books or films, to account for the player's active involvement in the investigation and solution. Relying on one "big question" to drive the story may not work, because player's actually have to solve it, but still have to be surprised for the thing to be any fun. A series of smaller mysteries that each function as a puzzle (i.e. you have to make one particular mental connection) is more promising, and the challenge is to weave them together in such a way as to create a coherent story and overall case.
I also made the murder victim, culprit and weapon different every time you play to make the game VERY replay-able.
I have a hard time seeing how you'd avoid the whole thing becoming arbitrary this way. As outlined above, I think the appeal of solving the mystery is realizing "Of course that's how it has to be! It couldn't have been any other way. It all makes sense now!" If you're designing the game so that any solution could be the right one, how do you make it seem like the actual solution is the only one possible? (I realize you change the clues and details a bit depending on the randomly chosen configuration, but story-wise most of it has to be outcome-independent, right?)