Have you looked at speak with dead? There are a lot of issues with it. It WILL NOT be an instant mystery solver. And most of the other ones, like legend lore? They are a mystery to solve themselves.
Precisely. Most spells, despite how they're often discussed, have limitations and failure-modes built into them; the key is that most characters living in the game world will know about those and take measures appropriately. The GM can then work that into the adventure.
If someone is murdered, and you use
speak with dead on the corpse, asking who killed them might get an answer of "they wore a mask, a white one with a red star mark on the forehead." Now it's a race to find that mask. Do they use
locate object? Maybe it's at the bottom of a river, discarded by the killer, but has a strand of red hair still stuck to the edge. Use
scrying on the red hair, and now it leads you to a tavern owner, who swears that the mask isn't his (and
zone of truth confirms it), but that he wore it as part of a play he participated in two nights ago. Time to investigate the other members of the actor's troupe!
Just like that, you've incorporated the spells into the adventure, rather than having them negate it.