For now I will put aside the question of how to make role-playing a mystery fun (these often turn into a boring series of dice checks that can dead-end the fun with one bad roll).
Many of my examples are criminal mysteries, because these are actually easier. The type of intellectual mysteries you mention are much harder, but I'll address those last.
No mystery here!
Mysteries are not terribly mysterious once you know all the facts. Something pretty straightforward happened. Someone tried to cover it up. As a mystery designer, start with the crime or whatever is secret, and then work backward.
Means, motive, and opportunity
These three things are the staple of detective stories and police procedurals. Means: did the subject have the ability to commit the crime. Motive: did the subject have a reason to commit the crime. Opportunity: did the subject have the chance to commit the crime.
As a mystery designer, address all three of these. Why was the crime committed? When? Under what circumstances? How did it go down?
The timelines of a victim and the person who preys on the victim are linked in at least two places in almost all cases. One provides motive and the other provides opportunity. Somewhere between those two, there's an event that provides means (for example, a murderer buying a gun), though it might not be a deliberate action. More links in the timeline offer more opportunities for PCs to figure things out; don't be stingy here.
Start putting together timelines but work backward, away from the central point of the mystery (usually the crime itself). If you have a murder, work backward in time from the murder. How did the murderer and victim end up in the same place? Was it an intentional set up? When did the murderer meet the victim? What happened?
Then work forward in time from the mystery. How was it covered up? What happened after that? Who stumbled upon it?
Everyone makes mistakes.
Well, everyone in your stories. Mistakes provide clues. Clues provide opportunities for PCs to solve a mystery. Work through your timeline and introduce subtle mistakes: aberrant behavior, missed appointments, entries in journals that no one was supposed to read, witnesses. You can also introduce not-so-subtle mistakes and "acts of God." A storm washes away the dirt over a makeshift grave. A worker stumbles upon a hidden brick wall. Stuff happens, and this gives the PCs a useful clue.
If you want to produce mysteries of a non-criminal nature, these rules should still work surprisingly well. There's still a secret that someone went to a lot of trouble to guard. Let's say it's a treasure. Apply the guidelines.
No mystery here. Once layed out, the mystery isn't very mysterious. Let's say that a woman hid a very large treasure before she died, but left a trail of strange clues leading to it. Why would she do such a thing? Well...
Motive: She wanted to leave the treasure to her daughter but couldn't tell her about it in time. She was dying and her daughter was on a camping trip in some remote part of the world. If she left a note, someone else would surely get it. In fact, her body is nearby the treasure. She also didn't want her archenemy to get the treasure.
Means: She was a mathematician and lover of puzzles. She had the ability to create a difficult set of mysteries leading to the treasure and hoped that her own daughter would remember the lessons she was taught.
Opportunity: The dead mathematician can be established to have found the treasure -- maybe she was seen carting it off somewhere before treasure hunters shot her.
Timelines: Create a timeline from her death backward to finding the treasure and even seeking the treasure. Somewhere in there, she gets shot, providing her with motive to hide it. Work forward from her death to the discovery of her death by her daughter (who could be a PC or a patron who hires the PCs or just a character in the papers who provides impetus for the PCs to go treasure hunting). Include in the timeline bits and pieces of the woman's puzzles (see below).
Mistakes: Work through the timeline. There's two mysteries here! One is a murder, the other a treasure hunt. Complicate the timeline with mistakes and acts of God. Life is messy. People saw stuff. Hikers discover a woman's body and she has the first clue in her pocket, in a journal. The clues will lead the PCs through the timeline and perhaps across the world in search of each next clue.
You could actually create these mathematical puzzles and ciphers and stuff. If your players enjoy solving these things, go for it! If they don't enjoy them, however, be prepared to just hand-wave it. It's okay to say, "You solved the cipher and it leads you to a library in a far northern village. You're supposed to look for a stained glass window." Abstract this stuff to some narration and maybe dice rolling when it stops being interesting to the players. Keep the action moving.
Research does help
Of course, a little research about real world mysteries can make your in-game mysteries seem more... well, mysterious! Maybe the players aren't going to actually solve any ciphers, but it won't hurt to tell them that it's a Vigenère cipher and mention briefly how it works. Or make a quick hand-out for the player who rolls to solve that clue, and let them explain to everyone (in character!) how it works and what it says.
Hopefully, with these suggestions, you are on your way to creating exciting mysteries. Nothing here supplants the requirement to be creative and devious. That's on you. But maybe this gives you some structure and constraint to spur on your wildest imagination!