This question is fairly specific to the shadow-haunted, torture-porn, evil Cenobite god worshiping country of Nidal in Paizo's world of Golarion, but could also apply to other "lawful evil nations" out there. Nidal is featured in the novel Nightglass as well as various Pathfinder supplements.
The PCs from my Reavers campaign were traveling cross-country in Nidal to go do the adventure The Midnight Mirror, they have a travel pass that lets them through to their destination in the otherwise foreigner-unfriendly nation. Anyway, they were out in the grasslands traveling from one county to another and came across some shadowcallers (local magical SS guys) pursuing some tiefling fugitives through the tall grass, one thing led to another, and they killed both of them. I didn't expect the fight, the shadowcallers were like level 12 and the PCs level 7 but they surprised them and got lucky with Stunning Fists... Apparently PC tolerance for "let me see your papers and root through your stuff" is pretty low even when there's possible horrific consequences.
They removed hands and jaws (no speak with dead and even raise dead becomes problematic) and buried them in a deep hole on the plains an hour away from the fight scene and made group Survival check at 28 to remove traces of the fight and 29 at the grave site (that would set the DC of a Perception/Track to discover the site). They took all identifying material off them including all magic items and went using a summoned mount and buried those in a nearby forest (didn't keep any of it). They used prestidigitation to clean themselves, the wagons, etc. of all traces of the fight.
There were no witnesses except the tieflings, one of whom escaped before the fight started and one of whom was killed by the PCs under the "No Witnesses Act" and given the same treatment as the shadowcallers. (They didn't kill the shadowcallers to save the tieflings, but because they were going to confiscate one of their weapons... They are neutral to evil pirates, not freedom fighters.) They're traveling via wagon in plains-type terrain for tracking purposes.
Assuming they'll be back out of the country in a week or so, I'm trying to figure out how much detection would reasonably be brought to bear on them in the interim. The shadowcallers' superiors will get concerned within a day or two, and then they'll need to mobilize, find the bodies, figure out what happened, figure out the party's responsible, find the party, etc. using magic available to, say, a L12 wizard or cleric max (the shadowcallers tend to be mystic theurges, shadow-themed wizardry plus worship of Zon-Kuthon). And torture, they like torture.
If they catch the tiefling then it'd be easy, but that tiefling is a lucky bastard - he rolled something like 5 natural 20s during the chase, eventually stealthing away from the shadowcallers and party before the fight even started. He's a rogue and has a bunch of loot on him from a burglary and is trying to make himself scarce. I'm going to assume he stays at large for another week at least.
How screwed are my PCs? What do you reckon the shadowcallers' timeline and tactics are here? It's Golarion so there's Pathfinder standard magic but it's not all "oh everyone has magical telegraphs and stuff everywhere." There's records somewhere in Nisroch about the PCs and their travel plans but it's unlikely someone else in the interior of the country would be able to quickly find out "names of every foreigner in the country" or the like to ask trivial divination spells "Did guy X kill them?" Assume reasonable medieval recordkeeping plus standard spells. How, specifically, can the PCs be found out?
Edit: I'm not looking for excuses to catch them or excuses to let them get away. I'm asking, given a country in which finding out what happened to these guys and hunting down their murderers is culturally desirable, what nonmagical/magical (Pathfinder) techniques can be brought to bear to ID and find the party and how long will it take? If they just "get away" when there was some easy divination way of finding them, then it's not very realistic.