There are two main parts to this rant, and they can be summed up like this if you’re not really curious: 1) Less fantasy authors should use mystery elements in their fiction, since they aren’t good at them. 2) The fantasy authors who want to use them anyway should not give them less respect because they aren’t climactic battles, the rebellions of young heroines, or romance.

1) Consider why you’re keeping certain elements of the story mysterious.

Quite a lot of them really don’t need to be. I’ve read fantasies where the heroine’s background remained obscure until halfway through the story, and then turned out to be an ordinary one, involving, say, a birth on a farm, a few arguing siblings, and her leaving when she turned sixteen. It wasn’t the source of any special skills or trauma for her. While I applaud the authors for creating more ordinary heroines than the superpowered stereotypes running around fantasies, I’m puzzled why they felt the need to keep it secret.
Or, perhaps, I’m not. I’ve found that I’m doing the same thing in my latest novel, Legend of the Singers, and after thinking about it for a while, I know why. I don’t want to tell everything, and I don’t have characters who would be thinking about the newness of their surroundings or their backgrounds at any minute, so I’m giving information away one piece at a time in order to avoid infodumps. However, while that’s a noble motive, it can go too far the opposite way, and the audience is left in the dark about the most elementary things for no reason. If the information isn’t important to keep secret, slip in little details along the way; don’t save everything until page 476 of a 500-page novel (see point 7).

2) Don’t strain the reader’s suspension of disbelief by over-reliance on red herrings.

A lot of fantasy writers doing political intrigue, even in published novels, have an obvious candidate for the villain, or plotter, or poisoner, or whatever. Of course, in its obviousness it’s wrong. The reader, especially if he or she is used to reading mysteries, will figure that out, and resent being pushed in this wrong direction with a pat on the head. “See? Believe that this person is the villain, even though you know he isn’t! Believe it because I tell you so!”
The revelations of the best mysteries are a total surprise and perfectly plausible at the same time. It’s pretty hard to do, but littering the story with candidates that the reader can see would never in a million years be the villain just clutters up the plot without advancing it. If you introduce a red herring, make sure it’s reasonable enough to get at least halfway through the book.

3) Hide clues in a mess of other details.

This is another part where simple inexperience has the fantasy mystery writer playing her hand too early. The scene where the important magical book that will reveal the past of the lost race appears for the first time spends about six adjectives on that book and one, or none, on everything else. Or the book shines and sparkles and “has a special aura,” even if that’s not the scene where the hero first reads it. Fantasy authors often give in to the temptation to use the authorial wink-wink-nudge-nudge too much anyway, witness the number of “cute” things many of them try to do with the omniscient voice. But in the matter of a clue, such attempts to sing the, “I know something you don’t know!” song will result in the reader guessing that there’s something about that object to know, pages or chapters before the author thinks they’ll get it.
The best thing to do is bury the clue, or person, or detail out of place in a massive descriptive passage that also takes notice of other, perfectly ordinary things. Here’s an actual good use for those purple prose monsters so many fantasy authors are fond of. If the character Rebaraanna is the traitor, have her appear in crucial meetings along with a number of other important people, not act eccentrically, do perfectly ordinary things that only later someone will connect with her betraying the Light side’s secrets to the enemy (such as gossiping, which lots of people do), and betray only secrets she could reasonably betray. Here the lack of consistency comes in again, coupled with the fantasy writer’s desire to create an absolutely untraceable villain. If Rebaraanna is betraying secrets that were only spoken in meetings that she was not present for, you either have to come up with one of those complicated mistaken identity/disguise plots, introduce a second traitor or secret passages, or go back and rewrite the scenes so that she only betrays things she could reasonably know. Or, of course, you can keep track of where she is and what she’s doing and avoid the whole mess in the first place.

4) Give the villain reasonable motives for pursuing a tangled, convoluted plan.

So your villain intrigues and backstabs and poisons his way to the top. Ask yourself this:
Does he really need to?
A villain who has magical powers that no one else can approach, or who is protected by his heart being in a glass casket beyond the Lake of Fire, or who is smarter than any of his opponents, really shouldn’t need to. I’m always puzzled by some of the things these people get up to in fantasy novels. They ignore the Keep It Simple, Stupid, rule and dive into political conspiracy and corporate ladder-climbing apparently for its own sake. Yet they also have personalities that don’t match their tactics. They don’t enjoy risk-taking, and they start panicking when the heroes begin to unravel their secrets, so that you wonder how they fooled anyone in the first place. They even sometimes lament how much simpler it would be to blow everyone away in a firestorm.
If they can, why aren’t they taking that simple route?
And no, as you may have guessed I was going to say, “Because I wanted to write this kind of plot and this kind of villain at the same time, never mind they don’t match,” is not a good answer.

5) Don’t neglect minor mysteries for the sake of the larger one.

Plot threads do get dropped in fantasy. Sometimes we don’t find out where a minor character went, or an author seems to promise a fulfillment of a romance that never materializes, or we don’t know for certain that the villain is dead (until the sequel, where we find out he wasn’t, so that the author can sell more books). A lot of readers are forgiving of this, since they might not care about the plot point, or understand that in epic fantasies the focus is on the main characters, not every minor so-and-so. However, with a fantasy mystery, such neglect is deadly. Mysteries have to be tightly woven patterns, in contrast to the big tapestries of epic fantasies.
If you start out the book with someone trying to kill your hero’s lady, and then use that to lead him into the web of a much bigger and more dangerous conspiracy, do not forget about the original assassin who struck at the hero’s lady. If it was an assassin from a smaller and less dangerous faction, he should still be concerned. Someone tried to kill the woman he loves! I would imagine that he should find that more interesting and compelling than the political maneuverings of a bunch of strangers he’s never heard of. (In fact, fantasies with a conspiracy element in general have a problem convincing me the hero would care about the villains’ shenanigans, which is something I’ll get to in the rant tomorrow). The lady herself shouldn’t forget about it, and neither should her family.
A Good Example of how to do this is in Glen Cook’s Dread Brass Shadows. The detective character, Garrett, sees his on-again, off-again girlfriend struck down on her way to visit him. That this turns out to be tangential to the main mystery is not the point. He still crashes after the man who tried to kill her, does his best to kill him in return, and goes home extremely angry and upset. This would have flopped if Cook had made Garrett just catch the man and try to question him about why he did that. Garrett’s motive in that moment is punishment, not intellectual curiosity. Suppressing your hero’s emotional reactions just to make readers admire your clever plotting Is A No-No.

6) DO NOT rely on coincidence to let your detective solve the mystery.

Ugh. No. Please. One more overheard conversation that’s only heard because the hero just happens to be coming back from the kitchen after a midnight snack, or because the villains are incredibly stupid and give the hero a room with a secret passage in it, or because—why not call it what it is?—the author is in there playing Hand of God, and I will explode.
One reason the detective subgenre of mystery thrives like it does is because readers take pleasure in seeing a clever mind unravel the details of a dastardly plot. It isn’t clever to have the hero wander by a room in which a key conversation takes place. It isn’t his intelligence that’s in play when he just happens to follow someone he sees leaving the castle because of that “Somehow, he knew he had to follow her” crapola and, gasp, she’s the boss’s evil henchman. Have him be suspicious, sure, but base the suspicions on his own reasoning about things, not on luck.
The cure to this one is to learn how to freaking plot—something good mystery writes shine in far more than a lot of fantasists. I think fantasists in general have better world-building and characterization skills, but if you try to write a fantasy mystery and you don’t know how to plot, characterization won’t help you a whit. A hero can be as intelligent as a dragon and still be dragged along by the author into unlikely coincidences, because she’s never learned how to arrange events so that they don’t seem unlikely.

7) Avoid the “explaino” finale.

You know. The one where the hero sits everyone down in a room and talks them to death with his clever revelation of how he figured everything out.
This is no more clever or wise than the villain bragging about his plans to the supposedly helpless hero, and yet fantasy authors still do it. This killed Lynn Flewelling’s Traitor’s Moon, which has a strong mystery element, for me. The hero went into an explaino, and everything sagged.
For gods’ sake, you’re still writing a fantasy, with its heritage of “this is so wonderful.” Don’t drop your book into an infodump in the end, especially if you’ve managed to avoid infodumps all the way through. Have the hero figures things out and go dashing dramatically to the rescue, or to be rescued, or to confront the villain. You know, the climactic battle you might write with flair and style, as opposed to the embarrassing ten pages of infodump that 99.99999% of the human race can’t pull off gracefully?
This is another reason to read the Vlad Taltos books (yes, Steven Brust again). The first two, as well as some others in the series, have strong mystery elements, and the hero figures them out believably—but he only spends a few paragraphs at the most explaining them, and they’re not at all the climax of the story. The climax is him killing people. Vlad is an assassin and a mob boss, not Sherlock Holmes.
Remain true to your larger setting as well as your mystery tradition—and the best mystery traditions avoid explainos anyway.

8) Don’t create a hero who could not act as a detective under any circumstances. Or don’t write a fantasy mystery using such a character.

Your typical easygoing peasant hero, who follows the Gandalf Substitute around and doesn’t ask questions about his mysterious manner, who has never shown any inclination towards curiosity or puzzles, who thinks the best way to deal with things is to attack them with swords or magic, would be a disaster in a good fantasy mystery. He doesn’t even ask questions about mysteries that concern him (I find the number of main characters who respond to “You’re not ready to know this yet,” with “Okay!” unacceptable). Why in the world would he probe into the mysteries that surround these people he’s only just met? Even if they convinced him his life was in danger, why wouldn’t he charge in, daggers drawn, and try to solve the problem that way? A typical fantasy hero, even more than an invincible villain, has no reason to go this route. Risk-taking makes a much more acceptable character flaw for a villain than a hero who’s supposed to carry the responsibilities of the world on his shoulders.
The classic traits of a detective include not only intelligence and centrality to the plot, which a lot of fantasy authors are willing to give their characters, but some curiosity, a “puzzle-solving mind” (as Guy Gavriel Kay names it), a distrust that means he’ll automatically start suspecting lies if people tell him things too freely, a willingness to look beneath the surface, an unflinching commitment to finding out the truth, and some stake in solving the mystery. It’s a rare fantasy hero indeed who combines all those things. Most fantasy heroes are honest and trusting to a fault, and they only suspect the obvious red herrings and “people who feel bad” that their writer arranges for them to suspect. Many of them are also in positions where truth isn’t their overarching goal, and if they’re trying to solve someone’s problems, they want to make them happy, not find out what really happened. A good detective hero will dig out the truth about the new crown prince being a conniving bastard who once contemplated murder, even if he would never do anything like that again. A good fantasy hero might well find this out by accident or the prince’s free confession, and then forgive him, or close his eyes to the truth because the prince has been honorable since.
Don’t try to write a fantasy mystery if you have a hero who has no stake in being a detective.

9) If you’re imitating a specific detective subgenre or mean to pay an homage to a particular author, study the conventions of that subgenre or author.

Here I’ll talk mainly about one of the few pure fantasy mystery series I’ve read, Glen Cook’s Garrett series. It’s ten books long now, and all of them are named after metals (Sweet Silver Blues, Bitter Gold Hearts, Old Tin Sorrows, and so on). Not all of them are equally good, but all are to be commended for taking a highly recognizable Philip Marlowe-descended detective character, Garrett, and plopping him down in a fantasy world. Garrett is a wisecracking character with Marlowe’s puzzle-solving mind, tendency to get wounded by the bad guys, and attitudes towards women. This means that this series is highly, highly sexist.
That’s part of the risk of such homage: the tendency to bend and soften the portrayal just a little, update it, and write a “better” version of that same detective. At that point, though, it becomes yours, and you have to take all the risks and rewards that a new subgenre implies, without being able to claim that you’re writing it this way because that was the way this other author wrote.
Cook’s way of doing this is never to forget that he’s writing that kind of P. I., and also never to forget that he’s writing that kind of P. I. in a fantasy world. Garrett has a background in military reconnaissance that comes from his country fighting a seemingly endless war against another country, a war in which every young man must serve for at least five years—and which has killed off a lot of those young men. (If this looks familiar, it should; Cook served in Vietnam, and that influences both this and his other major fantasy series, the Black Company, about a bunch of mercenaries). A lot of non-human races also call his city home, refugees from the war among them, which causes tension between them and the war’s veterans, and forms a major part of the ninth book, Faded Steel Heat. Garrett’s best friend is a sleazy half-elf. His “partner” is a telepathic creature called a Loghyr, which died four hundred years ago but isn’t ready to move on yet, so it sits in its chair in Garrett’s house and picks the minds of suspects and clients. And so Cook makes some sacrifices, but still gets to play with a lot of toys most other fantasists don’t even touch.
This will have to be a two-part rant. The one tomorrow will be about keeping the fantasy in the mystery.