I try not to get fancy with the clues. Once you start in with the puzzles and whatnot you've added another gate to solving the mystery, and one that will be a huge letdown if solved by a roll rather than the PCs. That's not quite the same thing as cryptic of course. That's actually a great tool.
Cryptic and incomplete information can be a wonderful thing for investigative games. For example, in the Duke's office, you find a letter that reads Things are spiraling out of control, we need to talk. Meet me by the fountain at last bell. M. That's a cool clue. The players get some solid info - the Duke is certainly into something that requires clandestine meetings, which could warrant some more digging, and now we have the mysterious M, another avenue for investigation.
When possible, I like to leave multiple lines of inquiry stemming from new info. Both the new things in the clue index the same path, finding out what nefarious plans are afoot, but the players have more than one way to check things out, or can split up and rock both at once. Rather than a trail of breadcrumbs, I like to think of the plot as an interconnected web of information, which multiple lines of connection between the moving parts. The players are a lot less likely to lose their way in a web than on a trail.