Few techniques I regularly use in my game. GM/spymaster techniques first:
Recursion 2+ - thats what you already did. The wealthy rarely sent some of their men to make the crime, but they hired a spy or assassin. Even wealthier hired their spymaster, who hired spies or assassins for certain tasks. Since link between a lord and his spymaster is secret itself, it's hard to track the lord. More iterations were almost unknown in Middle Ages, but modern agencies usually consider them a must.
To regularly break recursion-3 cases, someone must know lords wealthy enough for keeping such an agency and observe them to find out whether or not they have a spymaster. Once you know a spymaster, it's possible to connect him to the crime. Once you know a spymaster well, it's easy.
False flag operations - closely connected with the previous point. They were not as common as today in Middle Ages, but any advanced espionage net will probably use it, and it's a must for anyone taking into account mental magic (i.e. perfect interrogation techniques). If a spy says "I work for baron Sigmund the Sly", he probably lies, though he may not be aware of it (so normal lie detection spells/skills don't work in this case).
Alternate identity - for spying reasons, you need few alternate identities and disguises. Otherwise, you're too easy to track, and once your true identity is known, you might expect to return just to find your Covenant besieged by enemy army.
Always have someone to frame - extension of two previous principles: every time you do something risky, there must be someone else who is more suspect than you, and everything must point to him, not to you.
Never work alone - PCs can do everything by themselves, but they lose the advantages of recursion-X and false flag. Hiring, blackmailing or otherwise recruiting a skilled spy who's not officially connected with the PCs is better. On the other hand, until you have real spy network, you can't make your contacts do everything. They can't be everywhere and their cover can't be blown. And you need to trust him, but not too much...
Helpful rat - every criminal have some enemies, who might cooperate with PCs. But be aware, because enemy spymaster might have sent an agent to sabotage investigation or just gather intelligence on the PCs. This agent might be convinced he really work for a third side, but his orders say that the PCs are more dangerous for "his masters" than his true master, the enemy of PCs. Or it may even be true - there is some common enemy who sent and agent to help driving his rivals against each other.
Anything might be important - talk to everyone, listen to all the gossip. Or have someone who observes all the gossip for you. Intelligence analysis is the art of combining information together. It's impossible for the GM to give the players everything they hear, the players will have advantage of having much better "useful informations to clutter" ratio than real spies have. As the players get better and better at it, GM may add more and more irrelevant informations. Some of this intelligence might be even misleading. Or very useful, but not for the case you are actually investigating.
Just be curious - there are many people interrested in gossip. Bards, village/town women, barkeepers. All these people make excellent contacts and often they still don't realize they work in espionage - they think they just do their hobby.
Ask beggars - beggars usually know a lot and they're quite cheap to buy, and it's easy to approach them anonymously. The only disadvantage is that they often already work for some other spymaster/crimelord. When interrogating beggars, ask about clothes and jewellery - good beggar must have a good knowledge of and memory for status symbols, though memory for faces or names is just a small bonus.
Interrogation rules - while interrogated, problem about most people is not that they don't want to speak, but that they don't remember things clearly and they are too scared to remember. Be careful about people who give too many details - probably they just have too wild fantasy. Or they might be real criminals and they just have a prepared tale.
Nobody expects Spanish inquisiton... to use magic! - I don't know Ars Magica so well (I've read the rules, but it was quite a few years ago), so the magical part of the tutorial should be your work. But remember - magic must seem as something mundane for those who will investigate your actions, otherwise you will alarm both church's inquisition and your rivals in house Quesitoris, and that's not what you want. The less trackable the magic is, the better, but it's even better when everyone suspects some mundane thugs who obviously can't use magic.
Few tips on suitable spells:
- invisibility is a spy's silver bullet
- mental magic means excellent interrogation tool for uwilling suspects
- divination is priceless
- do PCs have some form of astral travel? What they can find through it? What are its limitations?