The presence of magic has a profound affect on mystery and investigation adventures. It not only impacts the clue-finding process, it also alters your villain's schemes. In a mystery adventure set in a fantasy world she can draw on the same magical resources to commit and cover up her crime that the players use to solve it. This is an idea I tried to commit to fully when we were working on Beneath the Banshee Tree for Sertorius. I am not going to reveal the details of how magic appears in the module (because I don't want to spoil it for players) but I am going to talk about the process and the things I considered while working on it.
Before doing anything I went through the spells in Sertorius to see how they might be used in the motive for a terrible crime and what spells the perpetrator could use to evade detection and pursuit. I had the advantage of getting feedback and input from Dan Orcutt and Bill Butler so I talked with them about what kind of villain the system might support in that respect.
This opened up a whole new set of possibilities, including motivations that wouldn't appear in a mundane campaign. In a world where magical duplicates and mind altering potions exist, a mystery plays out very differently. Out of this oddness, new kinds of clues emerge. Ultimately the mystery began to take shape around some of the spells in question.
Understanding the parameters of the spell in each case, how it would play out on the ground was something I gave a lot of consideration to. I don't like when adventures hand wave magic, making it work differently for an NPC than it works for players using the same spells or rituals, so I made sure I followed spells as written. I attempted to be as creative as possible within that limit however. I just didn't have spells do things they didn't do in the book and I imposed on the stated limits on my NPC.
After this I looked at the spells once again from the point of view of players trying to solve the mystery. I didn't do this in an effort to thwart potential solutions but to be aware of the solutions and also think of how the NPC might take those into account (provided the NPC knew about the spells as well). This step is really important in a mystery set in a fantasy or supernatural setting because there are simply tools at the player's disposal that don't appear in a noir mystery. They are not cheats, they are just tools. A player using a read mind spell or speak with dead spell is no more cheating than a player in a modern campaign using a cell phone or the internet to help solve an investigation. This allowed me to account for those solutions and mention them in the text of the adventure in case they came up.
Then I set about creating my locations, events and clues. For Beneath the Banshee Tree I wanted to do a twist on our standard "Events Timeline" so instead of a regular timeline where an event occurs on a given day or hour (provided no one intervenes) I randomized it, having ten different "mysteries", with one occurring each day as the result of a d10 roll. This seems like a pretty simple thing, and it is, but it really made investigations play differently. Somehow it breathed more life into it for me as the GM. It also meant all of my pieces needed to fit together no matter what results came up. I like it as well because its like dropping a bomb each day that keeps the mystery fresh.
For each event, I had to decide what the aftermath would be (i.e. the dead body found in the inn), what had happened, who was involved, what clues were present, and where these clues might lead. Factoring magic into these mysteries was important. Again, I had to decide what spells went into the indecent itself, what spells may have been used to cover up the incident, and how players using spells might find clues beyond just looking around the room or talking to people.
All this together produced a scenario that wasn't like anything else I'd run before. I have played a lot of investigation adventures, and included magic, but I don't think I've ever committed this fully to the magic and the system underlying it. Now it has become my standard approach when magic is present.