On the other hand, do they need to solve the mystery, does the party need to always succeed? I would say no; that failure can be just as interesting as success as long as the PCs have other goals.
So, there's a difference between "not succeed" and "stop the adventure". The latter is less about success, and more about the players still having a good time playing a game that evening.
Say, the group decides to try to recover the Eye of Argon, which they learn was buried in a tomb with Gorgorath the Malignant, some 300 years ago. They dutifully seek out the tomb, and a half hour into exploring it, they completely fail to find the one secret door that will eventually lead them to the tomb with the eye.
They have failed.
But also, in the real world, the players are now stuck sitting at a table with no clear idea of what else to do. The GM prepped this tomb, and doesn't have anything else ready to play this moment. The players can break out a deck of cards and play pinochle, I supposed, but the RPG for the evening is done.
The full form of "fail forward" is not just "have a success with consequence" - that's only one implementation. It is that failure doesn't stop you dead in your tracks with nothing else you can do.