One example of puzzle dependency that I noticed worked really well was in the remake of Silent Hill 2.
The initial section is open world in a town and progress is gated by a puzzle requiring the player assemble two pieces of a broken record, and then find a missing jukebox button and a coin to play the record in the jukebox.
The first broken piece is in the jukebox. The other and the glue to fix them is in a music store. The player might encounter either location first, but both have notes describing the weird behavior of a patron who smashed a jukebox up in a rage, then apologized and said they would “fix it”. The bar with the jukebox says he “headed toward the music store” but also that the character might need to be checked on and specifies where he lives. In the music store, the note says the character arrived in a rage wanting to fix the record but didn’t have the other half, and that it probably came from the jukebox in the bar - and I think mentions the character was preparing to leave and likely went home to do so.
In the apartment and around it notes are found by the character who wants to leave, saying they have “one last stop” at a diner, where the player can find the token needed to start the jukebox. The missing jukebox button is found in the character’s apartment - the building of which is another open area - the correct apartment is locked, but there are building notes about a “leak” in the apartment above another one with a key, which trains the player they can navigate around the building by connected balconies and fire-escapes between some apartments, or holes broken in the wall.
What makes the puzzle work is each location where something is found directs the player via in-world notes to one or more other locations where puzzle-bits can be found despite the order the player searches in - even though the puzzle elements are scattered ludicrously and must be searched for, there are clear designations of the general area where each can be found, and all can be found in random order. The player is never “stuck” unless they completely miss a key object at a location, and they can investigate other locations that will continue to direct them back to the correct locations involved in the puzzle.
This is a mess, but shows how the player is eventually funneled toward plot advancement.
I think the key in puzzle design is to avoid a bottleneck where a player has to do a specific thing, and that’s the only thing they can do. Side tracks should direct the player (albeit vaguely) where to go next.
The other handy thing in SH2 is the player has a map which is auto-annotated - if the player reads material directing somewhere, it is circled on the map, then checked off if the player gets the thing they need there.