Now, look at your campaign world and its' level of magic/leveled-people/etc, and really think about how that's going to affect your mystery adventures.
I don't know where to start, so I'm just gonna jump in somewhere random.
1. Timing. How long has it been since the crime/event happened? This can make a lot of differece. Survival-track is dependent on time, especially if using scent. Certain divination spells only go back so far. Casters need time to prepare the right spells. In a less mechanical sense; people have limited memories, so if it's been a while since something happened, they will remember it less and less. Also, people involved or witnessing crimes have a tendency to disappear after a period of time.
2. Where. An event that takes place in a stone room in a crypt somewhere is probably not going to have any witnesses, but the evidence should be pristine. An event that takes place in a crowded marketplace is going to have tons of witnesses, but the evidence is going to be extremely "corrupted".
3. Why. Was the event planned, was it spur-of-the-moment, was it an accident? What was the motive?
4. Who. Who did it? Who was involved in it? Who knows what? Who lied to whom? Who is lying to you? Who is involved, but doesn't realize they're involved?
5. Skills. Bluff is obviously a big one - even a lowly commoner can pull off a lie if it is believable and the target wants to believe it. Sense Motive is another big one - not just to detect a lie, but also to determine if someone is trustworthy, if they are charmed or dominated, or if something about the situation just isn't right. Gather Information can spread rumors as well as find them. Disable device can cause saddles/wagon wheels/various-other-things to fail unexpectedly. Open lock can get you in and out of places without showing signs of entry. Heal can determine cause/time of death.
Know: arcana and spellcraft especially can be very useful in magical mysteries.
Disguise, intimidate, diplomacy, know: local/history/nobility & royalty, forgery, sleight of hand, search - all highly relevant to certain mysteries, and are often combined in a single crime.
6. Spells. On both sides of a crime, spells are very important. Many spells can obscure a crime, and many can reveal it. Explaining them in depth would be a thread of its' own. More importantly, how available are the various spells to the people involved in the mystery? Every spell has a counter, if only it's available to the person in question. Can the person cast the spell themselves? Can they cast it from a scroll or wand that they bought or stole? Can they hire someone to cast it? If so, from where? And what did it cost them? Were there strings attached?
7. Monsters. Dopplegangers, mindflayers, vampires, fiends, dragons, and various other insidious monsters can make solving a crime into a maddening experience (not to mention extremely dangerous). Their innate abilities make them well-suited for crime.
Whether or not a mystery is challenging depends mostly on the players themselves, but also on the abilities of their characters.
A highly-skilled player playing a fighter can probably solve a crime better than a novice/idiot player playing a genius rogue/bard/cleric/wizard/ranger/whatever.
If all it takes is the use of a single skill or the casting of a single spell, then it probably wasn't much of a mystery. However, not every mystery needs to be great, in fact I'd say that most don't. Expending a spell to learn something potentially vital is a good use of a spell. If a character invested in that skill/spell, then they should reap the benefits.
When creating a mystery:
1. Pick a "prometheus"; the character who intentionally or inadvertently started the mystery.
2. Decide a motive; why did they do what they did?
3. Method; how did they do what they did?
4. Location; where did they do what they did?
5. Complications; what can make it difficult for the prometheus to pull off his mystery? what can lead the hunt to them? what can make it difficult to lead the hunt to them? Are there any second or third parties? Does the prometheus know of them?
6. Proxies? Did the prometheus use any toadies/goons/mooks/henchmen to get the job done? How many? How many layers of henchmen are there? (prometheus hires as assassin, the assassin hires some street thugs, etc.) Are they duped into participating? Were they coerced?
7. Dynamics; how are you going to throw it all together in an exciting and explosive (or subtle and devious) way? Massive three of four party battle in the crumbling remnants of the still-highly-explosive powder-mill with a cultist on the roof actively summoning a fire demon during a thunderstorm? The mayor getting poisoned in his bed the night after the big ceremony, after the party was rewarded for catching the "assassin" in that gigantic cluster-frick at the mill?
Don't spend too much time thinking about how difficult the mystery is for a group of players. In general, the more focused their builds are on combat, the less capable they are of solving mysteries. If they're combat gods, either keep the mysteries simple or expect them to be incapable of solving it on their own. If they are particularly well-rounded, you can throw just about whatever you want at them.
If the key-suspect ran off in the woods after committing the crime, and no one in the party has the track feat, they still have many options. Is there a tracker/hunter they could get to track for them? Do they have any animals that can track by scent? Can they acquire any? Can the party speak to animals who may have seen the criminal? Are there any fey creatures who can help out, if coerced into doing so? Can the party hire a diviner or a priest to determine where the criminal is? Can they guess where the criminal went? Can they just hire a detective if it comes to it?
A few more miscellaneous tips:
1. Your party is not going to do what you expect. Expect this.
2. They're going to miss your hint. Throw in several.
3. Leave at least three openings for the players to succeed, otherwise your adventure may crumble before it gets off the ground.
4. Play npcs' to their intelligence/wisdom/personality/training/background/alignment - don't be afraid to play evil people as evil.
5. Hook your players with potential rewards and/or by making it personal.
6. Vary it up. Crack open those books and use all sorts of stuff to make the adventure dynamic and interesting.
7. Add in a few complications or unrelated side-events to keep things interesting; chasing the assassin through the forest at night when werewolves/bandits/wild-elves attack (could even attack while you're fighting the assassin, turning it into a three-way battle).
I think that's about all I've got. Hope this helped.