Hi TJ. I haven't had a chance to play through Panic Room yet, but at the time I thought it was encouraging you recognized the problems with your first story and were working to address them with the next, and it's great you're still doing that. This is the right attitude to have, and I expect anyone looking at your profile in the months to come will keep seeing steady improvement there.
A murder mystery sounds fun, I've always thought we could use more detective stuff around here. And how complex it is to write really depends on what approach you take. There's dozens of ways to structure a CYOA, the key to not getting bogged down midway through is plotting out the branches ahead of time so you know exactly what works for the specific story you're trying to tell.
Also, where is when is this going to take place? If it's any real world setting, some research before you begin is going to be important. You need to at least give the illusion you know what you're talking about as far as the investigation, character attitudes, technology, etc. goes.
Sci-fi or fantasy allow you more wiggle room, but internal consistency and some level of common sense is still important for immersion there.
When it comes to structuring a mystery story for a CYOA, the first thing would be deciding if it's more a story or a game. Is the idea that the player is solving a puzzle, or is this primarily about the character experiencing and influencing the events of the story with the player steering them?
Either way, I don't agree with your assumption that the player shouldn't be allowed to miss a clue, or necessarily think you have to have the ending be exactly the same. (If that's what you consider the canon ending, sure, but sprinkling in a couple of failures or sub optimal endings is almost necessary for a CYOA.)
If this is a game, the player needs to be allowed to make mistakes in order to have eventually solving the puzzle be an accomplishment, and if it's a story, the character himself can drive the action when it comes to the really vital stuff--and the focus is going to shift a little from the importance of the clues in and of themselves to what the murder and solving it means to him personally, anyhow.
But what I mean about the character driving the action, is that they're presumably going to know they need to examine the scene, interview witnesses, etc. (or have a partner or boss that keeps them on the right track, if they're an actual detective.) The player would more be choosing how they go about it, and you just have to make sure there's enough there to keep the plot moving forward regardless.
For a more puzzled focused game, you might structure each section using time or locations, or some combination--say each day they can only perform a certain number of major actions, like picking from a list of witnesses or suspects (with some of them possibly opening up further leads), searching locations of interest or sending evidence you pick up off to the lab--and after a set number of days they either have enough evidence to make an arrest or various things may happen leading to an unoptimal end.
Fair warning, you're going to have to be pretty comfortable with scripting to keep something like the above from turning into a mess.
If you're going story focused...well, you just have to think of each major path as a complete story in its own right. (And ideally there really need to be at least two, I'm still not thinking the one single ending where the crime is solved and the criminals arrested is going to go over well.) A complete story doesn't have to mean the crime is neatly solved and the bad guys arrested, it just has to be some sort of logical and satisfying conclusion, narratively and emotionally.
Though if it's a classic style detective story you're writing, here are a few of the classic dos and don'ts:
The 10 Commandments of Detective Fiction.
(The site includes other writing tips from notable sources, some more serious than others...)