Secondary-World/Historical Fantasy with "Mystery" element

Sorry for the overly specific subject. :) I'm looking for recs of fantasies that have a central plot element of characters solving a mystery or just plain "figuring things out", as opposed to adventuring to defeat the bad guys or political maneuvering to make sure the right people gain/retain power. (Not that most books won't have a mix of those things, but I'd like the mystery-solving to be center stage.)

As the subject mentions, I'm particularly looking for something that's not in the real world or a historical/pre-industrial time period. I've never been able to get into modern-day/urban fantasy, so the Dresden Files and that brand of supernatural detective stories just do not appeal to me at all.

Some examples of the sort of thing I'd like to find:
List of Seven (Mark Frost) / Death of the Necromancer (Martha Wells) / Lady in the Loch (Elizabeth Scarborough) - Stories set in Victorian(-ish) settings with strong investigative plot-threads.
StarCrossed (Elizabeth C. Bunce) - A "bottle" sort of story, with characters all trapped together in a castle and our heroine figuring out everyone's secrets.
Idylls of the Queen (Phyllis Ann Karr) - Arthurian murder mystery

Also, as a related "what was that book?" question: A few years ago, I saw a book that I believe was a murder mystery set in a castle where the main character was the captain of the guard or somesuch who could see ghosts (or saw this particular ghost, anyway). Does that ring any bells? I feel like it popped up a lot on Amazon for a few months, but I didn't save it off anywhere...

off the top of my head:

Elfland
Midnight Riot
Among Thieves
The Affinity Bridge

Glen Cook's Garrett, P.I. books are a series of hard-boiled detective novels set in a made-up fantasy land. They're like the inverse of the Dresden books.

Joel Rosenberg's D'Shai
Susan Dexter's The Wizard's Shadow

Ghosts in the Snow by Tamara Siler Jones

re #5: That book, and especially its sequels, is definitely in the "mystery" category, but they do get quite gory. Just FYI.

I would second Joel Rosenberg's D'Shai and sequel, it has a murder mystery that's set in a rigidly structured fantasy society where there are 52 different "ways" or professions and everyone has special talents in line with their profession (except, of course, our protagonist, who didn't inherit his family's acrobat skills).

Fanuilh and sequels by Daniel Hood has an amateur detective in a fantasy setting- Liam, a traveler and former soldier etc, inherits the familiar of a wizard acquaintance and has to solve the mystery of the wizard's murder in the first one.

Shade and Shadow by Francine Woodbury is an academic fantasy setting, the chairman of the modern magic department is murdered and the main character/prime suspect, antisocial professor Raoul, has to clear his name.

Randall Garrett's Lord Darcy series (starts with Too Many Magicians and continues in a couple of volumes of short stories. This is a fantasy/alternate history Sherlock Holmes pastiche. Michael Kurland continued the series after Garrett's death. (As a side note, Glen Cook's aforementioned Garrett, P.I. is named in honor of Randall Garrett.)

Simon Green's Hawk & Fisher are hardboiled fantasy detectives. They have some backstory in one of his earlier books, a more typical fantasy, Blue Moon Rising. Green's books can get a little violent, which isn't personally to my taste.

The books Steven Brust's Vlad Taltos series (starting with Jhereg) often have some mystery elements to the plot, but they aren't the focus.

It's been a while since I read it, but I seem to remember that Patricia Wrede's Mairelon the Magician and sequel had some mystery elements. These are a kind of alternate-history Regency London with magicians. I had a little bit of a problem keeping track of the secondary characters too (the names seemed all quite similar).

I seem to remember Shariann Lewitt's First and Final Rites having some mystery elements too, but I couldn't get into it at all- the characters seemed flat and infodumpy.

Perhaps:
New Amsterdam by Elizabeth Bear;
Anno Dracula by Kim Newman;
The Somnambulist by Jonathan Barnes;
The Strange Affair of Spring-Heeled Jack by Mark Hodder
Guards! Guards! or Men at Arms by Terry Pratchett

I haven't read your examples, and this may be too urban for you, but Zoo City by Lauren Beukes, set in Johannesburg, is very good.

Point of Hopes by Melissa Scott. Strong mystery, wonderful worldbuilding.

@ Niko...could your "what was that book" request be Ghosts in the Snow by Tamara Siler Jones? Here is the description I was able to find...

"A mysterious killer is stalking and savagely murdering servant girls, leaving no clues behind nor any witnesses, except for the gruesome ghosts of the victims, apparitions that are only visible to Dubric Bryerly, head of security at Castle Faldorrah, who must resort to unconventional methods to stop the rampage, save lives, and protect the future of Faldorrah itself."

These were already mentioned in post eight, but the Watch arc by Terry Pratchett. The main characters are all watchmen and women in a large fantasy city. They are basically like normal detective or mystery novels but set in a fantasy world. There's seven of them, and a new one is coming out this fall. The first is Guards! Guards!

12: I think it's cause your Guards! Guards! needs a space.

The spirit lens by Carol Berg and Tea with the black dragon by r. a. macavoy might fit the bill.

There's often an element of mystery in Barbara Hambly's works, as she writes suspense novels as well as fantasy. My favourite, Those who hunt the night, is ruled out as it has a Victorian setting, but Dog Wizard and The dark hand of magic are set in different worlds.

<12 Thanks! I'll go and correct that.

12

They did a series of D&D tie in novels.

Murder in Cormyr by Chet Williamson (Forgotten Realms)
Murder in Halruaa by Richard Myers (Forgotten Realms)
Murder in Tarsis by John Maddox Roberts (Dragonlance)

Also there was a short story Anthology:

Realms of Mystery edited by Philip Athanas (Forgotten Realms)

also in the Warhammer Fantasy Universe:

Zavant by Gordon Rennie (Although this may fall a bit on the Occulty Creature Fighting side)
A Murder in Marienburg by David Bishop (Based around a Watch Station in the worst part of town)

I'll add a recommendation for the Hawk and Fisher series by Simon R. Green (It's a bit shaky at the start though)

I'll strongly support the idea of the Lord Darcy books by Randall Garrett (he's a detective in an alternate world where the Plantagenets *did* conquer France & still rule both countries, and where magic works like a science)

If you like Victorian-flavored stories, and don't mind a YA feeling, try Philip Pullman's series starting with The Ruby in the Smoke, featuring a plucky young woman probing her father's mysterious death (in the first book).
And for Victorian atmosphere with a somewhat similar nature, but not fantasy either, you might step outside the genre with Fingersmith by Sarah Waters: a gothic-flavored tale of suspense & intrigue. It plays tricks with your mind.
Although both are in the "real world", they seem far away, and should appeal to many fantasy readers who like some of the elements you listed. (One of the good ideas from the current library readers' advisory movement is to try books in a different genre but with similar "appeal factors".)

Seeing above that my post still did not go completely through I'll try again.

13

Although I adore Midnight Riot, I'd say it falls firmly in modern day Urban Fantasy detective stories with The Dresden Files, and therefore is not what the OP wants. I do highly recommend it to anybody who does like Dresden, though.

17 reminded me, Robin Wayne Bailey also did a fantasy detective novel in the Greyhawk setting, Night Watch. I haven't read it, but when I saw it in the bookstore it wasn't even apparent to me that it was a tie-in.

Dave Duncan has an excellent series that would fit the criteria, starting with The Alchemist's Apprentice set in a historical venice where at least some magic works.

Keith R. A. DeCandido's Dragon Precinct and the sequel Unicorn Precinct are both murder mysteries focussing on the guard of a fantasy city, involving all the usual fantasy tropes.

I also second the recommendations for the Lord Darcy and the Garrett, P.I. books.

It took me a while to get back to this, and wow, thanks for all the suggestions, y'all! :) Lots of options to poke at.

And yes, Ghosts in the Snow was the one I was trying to remember. I'm glad I asked, because my memory of the cover looked *nothing* like the actual cover, so I probably would never have clicked into it in my quest otherwise. :)

Servant of the Underworld is a mystery, magical fantasy set in the world of the Aztecs circa 1480.