Several years ago I was Googling markets for short mystery stories (I do that from time to time) and stumbled upon a site called, believe it or not, Better Holmes and Gardens. When I investigated, I found submission guidelines for a publication I hadn't heard of before: Sherlock Holmes Mystery Magazine. That's right--yet another MM.
Like all mystery writers, I love AHMM and EQMM, and I also submit a lot of stories to other current magazines that regularly feature mystery fiction, like The Strand, Woman's World, Over My Dead Body, Crimespree, Mysterical-E, BJ Bourg's Flash Bang Mysteries, etc. But the truth is, there aren't a lot of markets out there anymore--paying or non-paying--that specialize in mystery shorts.
Holmes Sweet Holmes

My latest is in Issue #19, and appears alongside tales by my friend Jacqueline Seewald and my fellow SleuthSayer Janice Law. I've not yet read all the stories in the issue, but I've read Jacqueline's ("The Letter of the Law") and Janice's ("A Business Proposition") and they're excellent as usual.
Anytime mystery magazines are the topic, I find myself thinking about those that have come and gone, over the years. A few were receptive to my stories and a few rejected everything I sent them (sort of like some of the magazines that are still around), but I think I tried them all. And I thought it might be fun to take a quick trip down MM-memory lane:
Mystery mags of the past
- Murderous Intent Mystery Magazine -- One of my favorites. Margo Power, editor.
- Crimestalker Casebook -- Andrew McAleer, editor. Boston-based.
- Mystery Time -- a small but wonderful little magazine. Linda Hutton, editor.
- Blue Murder -- I think I remember trying these folks and getting rejected every time.
- Red Herring Mystery Magazine -- RHMM published two of my stories, accepted another, and disappeared.

- Mouth Full of Bullets -- BJ Bourg, editor. Loved this magazine.
- Whispering Willows Mystery Magazine -- Short-lived. I barely remember this one.
- Heist Magazine -- Australian, featured stories only on CD-ROM.
- Crime and Suspense -- This had some fine stories during its short run. Tony Burton, editor.
- Nefarious -- Online-only, if I remember correctly. One of the first e-zines.
- Black Mask -- Again, before my time.
- Detective Mystery Stories -- Print publication, editors Tom and Ginger Johnson.
- Orchard Press Mysteries -- This was an early e-zine as well. I had only one story there.
- The Rex Stout Journal -- Another short-lived print magazine.
NOTE: Please let me know if you remember some of the many that I've overlooked--or if any of these I've listed have taken on new life.
Square pegs, round holes

Now and then, even so-called literary magazines will feature a mystery story: Pleiades, Thema, Glimmer Train, Phoebe, some of the college lit journals, etc. Tom Franklin's short story "Poachers," which won an Edgar and appeared in The Best American Mystery Stories 1999, was first published in The Texas Review.
Anthopology
Finally, any discussion of mystery markets should include a mention of anthologies. I usually find them by Googling "anthology calls for submission" and checking Ralan's Webstravaganza, which is advertised as a science-fiction site but doesn't limit itself to that. The two advantages of anthologies over magazines, I think, are that (1) anthos usually request submissions in a fixed window of time, which can be a plus if you hop in right away, and (2) they are often "themed." If you happen to have a finished story that fits their theme--or can write one quickly--you'll already have a leg up on the competition. Another excellent site to check, for mags as well as anthos, is Sandra Seamans's My Little Corner.

A leading anthology for mystery writers is of course the "noir" series produced by Akashic Books, in Brooklyn. Several of my SleuthSayers colleagues have graced those pages, and one of my stories will be in the upcoming Mississippi Noir. Other anthology possibilities are the annual "best of" editions that feature stories published during the previous year, like Otto Penzler's Best American Mystery Stories series.
And that's it--I'm out of examples. I'll end with a question: What are some of your favorite short mystery markets, past and present?
May the ones we have now last forever.