I began my last campaign with a murder mystery. Lemme see if I can remember the broad outlines:
Joe is a powerful, doddering old millionaire from old money.
Linda is from old money too, but her family is on its way down: next time her bills come due, she's losing the family estate.
So she hires a group of low-level creeps to help her out. One of them infiltrate's Joe's household staff and begins poisoning him with a wisdom-draining poison. Another one creates a Philtre of Love, and manages to slip it into Joe's food just as Linda comes on the scene. The third acts as muscle.
The plan is to get Joe to fall in love with Linda, marry her, and then let him die a "natural" death so that she inherits his estate.
HOWEVER, Bobby the Gnome, a slave at the local baths who's made a profession out of blackmail, figures out a bit of the plot, and blackmails Linda for his silence. Linda pays Bobby with a beautiful necklace that Joe had given her, part of Joe's dead wife's collection. But Bobby asks for more, so Linda has him murdered by the wizard creep she's employing.
The PCs were on the scene when the murder happened--the killer turned invisible right after offing poor Bobby, and they had to proceed from there.
Okay, this scenario ain't one you can use, but I think I did a few things right:
1) Twist the Plot. If it's twisty, then you can hand out the clues freely without giving everything away at once. Twistiness allows PCs to make real progress, but still take a few sessions to solve everything.
2) Everyone's got secrets. When the PCs find out the murder victim wasn't an angel, it noirifies the scene. The PCs had some purely helpful allies, sure, but they also got the runaround from Joe, Joe's adult daughter (who suspected them of being in cahoots with Linda), Linda herself, Bobby's wife, and so on.
3) Variety of bad guys. The PCs got in a couple great fights against the low-level creeps, but also had a lot of fun facing off against Linda in some purely diplomatic scenes: they knew she was up to something, but didn't quite know what it was.
4) Bad guys who are active. When the creeps found out the PCs were on their tail, they set up a couple of ambushes. When Linda found out, she first tried to move things along by arranging for Joe's death (covering up the evidence), and then, when that didn't solve her problem, fled town, elading to a fun chase.
Good luck with it! I love murder mysteries.
Daniel