The players in a Call of Cthulhu game can absolutely solve puzzles and mysteries, in a very similar fashion to how they would if playing an escape room game. For many people, this is literally part of the appeal of investigative games -- actually, as a person in the real world, solving puzzle (while doing so in character). That they are doing this through the characters in the game doesn't change this fact. This doesn't mean the characters aren't also solving the puzzle.
Conversely, a lot of people would not be happy with an escape room game where there was not a clear correct answer to the final puzzle, but "success" or "failure" came down to a random check. In this case, the players are not actually solving a puzzle at all.
So a couple thoughts in this.
First, and simply, describing the process of Brindlewood Bay as “a random check” is way off. It’s like saying that a CoC game comes down to a “random guess” by the players. It ignores so much of what is happening in play.
More importantly… as far as addressing the gap in understanding here… what’s being talked about most of the time when the word “mystery” is used in a traditional game like CoC is a puzzle. If the point of play is to solve a puzzle, then yes, I imagine most folks want some kind of solution to be known ahead of time.
What often happens in these discussions is people begin to talk about how something “feels”… and they then proceed as if that is not a subjective matter.
So if we want to talk about what makes for a satisfying puzzle to solve… then a solution becomes a pretty obvious requirement. But instead, people say that some players want to “solve a mystery”, or in this case, that they “want to solve a mystery instead of tell a story about solving a mystery”. But then we’re shifting into subjectivity. What type of play “feels like solving a mystery” will vary.
So to me, both types of play may feel like solving a mystery, depending on the participant. Neither of them are actually doing so,
Both Call of Cthulhu (and similar games) and Brindlewood Bay (and similar games) are games about investigators attempting to solve a mystery. They have different methods of producing the outcome… both the “solution” to the mystery and whether or not the investigators succeed. Different folks will have different preferences about which game is better or “feels like being an investigator” or what have you.
Neither is “closer” to solving a mystery. I would say that they have much more in common with each other than either has with a real life investigation.