In addition to the listed above...
Collection of fantasy mysteries: The Dragon Done It, edited by Eric Flint & Mike Resnick.
Intro,
book page.
Retief! by Keith Laumer and
Retief's Peace by William H. Keith Jr. chronicle the adventures of Retief, who often has to apply his deductive powers to thwart whatever enemies are plotting against Corps Diplomatique Terrestrienne.
John Ringo's
Princess of Wands contains a take on "Ten Little Niggers" with a supernatural twist.