I used something like a murder mystery in my last game. The local King had always been a nice, fair guy. Then he got killed by assassins, and the PCs had him surreptitiously raised. Soon afterwards he started acting insane; highly paranoid, highly suspicious, with erratic behavior. The PCs, sworn knights of the crown, wanted to find out why.
Divination and research revealed that when the King had died, his soul had gone to Hell. The subconscious knowledge of that was breaking him now that he was alive again. The heroes decided to do what they could to save his soul, and thus cure him.
They ended up discovering the body of a young chambermaid behind a 20 year old bricked-up wall. The heroes concluded that the King had accidentally killed her and had had the body hidden instead of dealing with it. The group confronted him and convinced him to confess and seek penance; in a very emotional; scene he did, and the insanity broke.
All this happened in the midst of a paranoid manhunt and insanity-inspired civil war that had the King insisting that the PCs choose sides between the insane king and his reasonable but rebellious younger brother.
-- o --
Moral of the story? Consider coming at a murder at an oblique angle. Start with the murderer acting weird, then have the PCs detect why, and find out about the concealed murder from there. Throw in difficult moral quandries. What if the murderer is a friend of the PCs? What if the murder was for the greater good?