The Last Express sounds like a good game regarding what you're looking for. From what I understand, it's an open-ended mystery adventure game which you can fail at and have to start over if you don't make the right choices.
I'm not really sure if I know about any other
open-ended adventure games. Certainly I know of adventure games where death and/or dead-ends are a real possibility, and at least one where major puzzles can be solved in multiple ways (KQ6), but in that case they only somewhat affect the ending cutscene.
I think the sort of game you're looking for also depends on what sort of setting-genre you're interested in (eg. fantasy, horror, sci-fi, etc.), and how well you deal with ingame deaths and/or dead-ends.
Phantasmagoria comes to mind as a game where there is somewhat of a mystery to be solved, and you can most certainly die, but death does not cause the game to restart (instead, making you go back to before you died and try again). The
King's Quest series (and free
fan remakes), among other old-school Sierra adventure titles do include death and dead-ends, such that if you don't save regularly there's a potential for really screwing yourself over, but I wouldn't call them "mysteries."
Also, I haven't played it, but I hear TTG's
The Walking Dead is potentially open-ended and includes death, though such death is not game-ending like you may want. It also doesn't have dead-ends.