At the end of the day, D&D is a very poor fit for these sorts of games, as it's model for everything except combat is either "roll that skill check" or "a wizard did it." In summary, witnesses are worthless, gather information, survival, and search are useful skills that either attack flat DCs or the opponent's bluff, Ebberon's Urban Tracking is essential to enable these sorts of adventures, and Detect Thoughts cuts through about 99% of the paperwork of a trial, and is a very common second level spell.
From a criminal justice standpoint, mortal-based evidence is all sorts of suspect. At the end of the day, like most investigations, it's one side's resources and expertise against another. It's genre specific though, so if your genre presupposes daring feats of thievery, they're possible.
We will presume that the group is interested in this sort of thing, and the game will therefore not feature the Omniscificer who, at level 4, can know every finite fact about the universe (including who did it. For completely arbitrary values of it.)
The first, and most boring route is actual forensic investigation of the evidence. Search provides clues at a location that are a function of the investigative technology of the genre. Note well, "evidence" is not actually useful as a discrete thing. There are skills (gather information, search, survival) that allow abstraction across multiple "clues" for tracking, and the whole idea of a jury trial which provides for witnesses and evidence is manifestly silly assuming access to a third level caster. There are no mechanics for the subsidiary questioning of evidence in a courtroom, nor is there need for it. Evidence allows a nominal perp to be found, not convicted, and all of that "tracking" is abstracted away from the game, to better allow an exciting battle at the end.
Beyond search, an investigator with the track feat can use Survival to track tracks back to the tracker's lair. There exist feats in Ebberon (Urban Tracking) that use Gather Information to the same effect.
Given that the DCs go all the way up to 20, (call it 30 what with one thing and another) and don't scale with the thief's skill, any sufficiently motivated constabulary should be able to find the target without resorting to divinations. In a high-magic game, CSI squads would all be issued magic doodads (keyword "Enhance!" that provide game-specific bonuses to skill checks. An item of Divine Insight made by a high level cleric of the god of justice would fit well here, But is rather overkill.)
So, presuming this, the rules overwhelmingly favour the investigator, save for the unfortunate fact that when they show up at the
Murderhobo's adventurer's hideout, they'll be murdered by the PCs.
The second major route is personal evidence. While witnesses are completely without worth, there are a couple of ways of asking "did you do it?" and being pretty sure of the answer. For the overwhelming number of (non-stupidly high level or optimised cases), once you've followed the perps to their lair, and "arrested" all of them, stick them in a "normal" jail for a while. Normal, in this case, being a jail that ensures that they can't regain spells and ensures that all of their normal buffs will have worn off. Then, simply, they're brought before a Level 3 magistrate (cleric or wizard or bard) and asked to let them probe their minds. Happily, there are no constitutional protections against self-incrimination in D&D, and I doubt that even lawful good societies would accept a nominal right to privacy considering that the idea, itself, is an extremely modern concept.
Therefore, the magistrate casts detect thoughts, and calmly asks the person under suspicion to allow the probe (in whatever lingo of the day.) Detect Thoughts is a level 2 spell, Whether knowledge of "core" level 2 spells counts as Common knowledge is a function of the tropes embraced by the game, but given that this is an acceptable and rather more humane form than typical of justice, it shouldn't come as a shock.
Refusal to "open your mind" is taken as a confession of guilt and the sentence is carried out. Once detect thoughts is properly calibrated (3 rounds of glaring at the perp), the perp has to beat a DC 100 bluff check to disguise their surface thoughts. Without access to magical resources, only the most elite will be able to do this (nominally through the use of some sort of prestige class.)
Unfortunately, while there are ways of gaining positive evidence of truthiness via spellcasting (detect thoughts, etc..), the best non-castery way of doing this is via the hunch trait of sense motive, which provides a "Alternatively, you can get the feeling that someone is trustworthy." Sense motive is useful to detect traces of magical coercion (DC 25, sense enchantment), but again, is made obsolete by detect magic. Fundamentally, the investigative aspect of law enforcement is sufficiently rare in a fantasy society to allow for dedicated "experts" to do it. (For a low-magic exploration of this, see Four and Twenty Blackbirds), by Lackey.)
Which leads us to the third, and most depressing way of crime fighting.
"God, did the perp commit this crime?"
There is a huge list of spells that do this.
- Identify Transgressor, which is somehow evil, gives a 70% correct answer. To get a 95% confidence interval, A panel of 3 drugged judges must each cast this spell.
- Probe Thoughts, higher level, can be used for things that are conevably within the interest range of high level characters.
- Susurrus of the City, worth enchanting into an "intentionally" abandoned building, allows for functionally unlimited questions about a city. It doesn't lie, and it's functionally omniscient for events within the city. A rather rare class from a rather rare book, it's possible that the city has kept this spell hushed up.
- Divination, of course, runs at the same error rate as Identify Transgressor. But having a panel of diviners on hand is simply common sense of any settlement that expects to deal with mid to high level adventurers.
Almost all of these spells can be foiled due to DM intervention (A god says "no") or high-level spellcasting. At the end of the day, there's no such thing as a long drawn out trial, since there are so many ways of asking "did you do it?" from the magical spirits/ether/gods/person. Functionally, this question resolves on the tropes chosen in game and the resources the DM is willing to grant the enemy. In a high-magic, all splatbooks game, crime only functions due to the corruption of officials. With the right splatbooks restricted, it becomes far more difficult to gather evidence. With magic restricted, it becomes much harder to ask "did you do it?"
From a criminal's perspective, it's very hard to keep these capabilities secret from either a Gather Information check or a Knowledge (Local) check. None of the things above really lend themselves to NSA style obfuscation, and given that successful criminals survive to pass their knowledge on, the Lamarckian evolution that therefore occurs makes this knowledge easy to pass on. In any world where the rules are given more than lip service by the NPCs, DC 20 knowledge (local), knowledge (history) (always handy to have a bent scholar around), or gather information "How did the coppers find Joe?" as well as the belief in the deterrent effect of punishments makes methodological hiding basically impossible, save for the very greenest of thieves. Therefore, the criminal knowledge of methods will operate much like it does in our world. Most criminals will have a working knowledge of the system that they're opposing. Good criminals will have better knowledge, and the rookies will die/get caught before they gain that knowledge. Given that you have a community of thieves ferreting this information out, all they have to do is beat the DC by 5 every time to get actual details of the method.
But, at the end of the day, investigations are a function of the adventure requirements. If they happen too often, consider playing in a different system.