I too am writing a mystery in a fantasy setting, mine is more of a humans only high fantasy setting as opposed to a modernish technology type, but the principals are the same.
A lot of the issues stem from not having strict boundaries on what your magic/tech can do and what limitations it does have. If you're working in a setting that has a VERY long history of magic like teleportation, intangibility, illusions, etc, people would naturally have created ways of negating these things around bank vaults, throne rooms, personal studies for richer folk, and holy areas. You also have magical spycraft to work with, and the wards that spies might set up when relaying messages.
You have a wide variety of reasons for people to ward against magic, and enough time scale that your setting will have started to use them a long time ago.
Another thing to take note of would be how far along is the technological advancement of magic in your setting. You clearly have widespread use of magic, most commoners are going to know everyday useful spells (sparks to start fires, purify water for drinking, telekinesis for reaching areas that they otherwise couldn't, etc.) While more complicated spells like teleportation, intangibility, and illusions are most likely bordering on forbidden magic, if not heavily regulated by the local government (like a drivers licence, or a hypnotist's licence in modern day).
A suggestion is to start by looking at your PCs sheets, and figuring out what spells the party has access to, your players will likely already know the ins and outs of their spell list, often better than you. Narrowing the method to one that the cast already knows, gives them a clue into what they are looking for. (especially if it's a specific class only spell or something like that)
My setting is a magic-is-rare type, or I should say, what WE as an audience deems magic is rare. What the characters deem magic is a bit more broad, and people who do magic are 1 out of 150. Magic is technology, religion fuels the magic, and the priests are in charge of too much management of society to do much in the way of advancement of any of it.
So when I do use magic in a murder, it /really/ narrows down the scope of prospective murderers. Its more difficult on my detectives, one of which is a sanctioned police officer, and the other who is a very low leveled priest of thievery and who is almost laughably bad at magic.
I have tailored the crimes they go up against specifically for their skills, i will admit my setting makes it one hell of a lot easier to narrow down stuff than yours, but it's still easy to say that individual schools of magic have signatures to their magical auras because everything they learn gets filtered through a specific grimoire or something.
The trick is to flesh out your setting well enough that YOU know all the little threads hanging onto your antagonist. It's also why I think i'm having such a hard time finding high fantasy murder mysteries as opposed to noir fantasy ones. You need a lot of setting details to do this right, and it's even possible to hide clues for future mysteries in earlier ones.
Although 'clues' might be a strong word, think of it more as background details and foreshadowing. If we find out about a red herring magic school in our first mystery escapade that specializes in water magic, it has no bearing on THIS plot (where the mystery revolves around a telekinetically floated knife stabbing a guy through the frontal lobe- maybe) when our intrepid heroes are looking into possible schools of learning that this guy came from, but in the next plot you can easily have a water magic based crime. Lending credence to your side details, and enticing your players to really explore your world as it unfolds.
It depends on how long you want your story to go, where you want to take things, and your party. Running a murder mystery right off the bat with your PCs, you're going to want to keep the /first/ one simple, as mundane as possible. After that, and your setups can get more complicated.
Stakes are a good thing to examine, commoners in a small farming village are a lot less likely to come into contact with crazy wild magic, while local lords and their hired wizards are far more likely to do so. I don't have my party solve anything higher profile than a local land owner getting stabbed by an iron sickle until they've gotten known in setting for solving murders, and even then, they don't see anything extravagant until after they take down the ringleader of a multi-national illegal artifact smuggling ring who has been using the curses attached to the stolen goods to kill off people in his way. After that, then they get into higher profile cases, including crazier locked room mysteries at major temples, murders of foreign dignitaries, and eventually they get sent out to foreign lands to solve murders for allied countries as dignitaries themselves.
This is over the course of years in setting, and I set out to have a detective series from the start. So look at your overall story and examine just how you want this arc to fit in with it.
Good luck.