Unfortunately, blood biography combined with magical checkins and a spell-based binary search (probably using spirit planchets and generations of "retired" agents as spirits) to locate bodies spells doom rather cheaply as government spending goes.
Blood bio, cast with a drop of a ctreature's blood, gives answers to:
Who are you? (The name by which the creature is most commonly known)
What are you? (Gender, race, profession/role)
How was your blood shed? (Brief outline of the events that caused its wound, to the best of the victim's knowledge)
When was your blood shed?
Finding the corpse will have blood in its wounds, which then provides a "brief outline of events." It is reasonable to assume that a brief outline will discuss the method of attackers. Which then, (papers please!) will link them to the last internal checkpoint by their class descriptions or other characteristics linked to their identities.
To be clear though, the public side of things will be absolute silence. Because the public doesn't know about this appearance of weakness, there will be no advertising the weakness. (Otherwise people get the idea that harming the secret police is possible, and we just don't want that...) Reprisals are fine and all, but an aura of omnipotence is better. If the team missed any of its checkins or procedures, their supervisor (to the function of his ability to have fall-guys) will be tortured to encourage the others. If there are some rumors, some of the "usual suspects" will be rounded up and executed for a trumped up charge.
In terms of team notification, every team will, being lawful, likely follow "modernish" police practice of "check in with home base." The logistics of this vary, depending on infrastructure.
- Visible tech: A napoleonic semaphore is not out of the question, especially with items of "whispering wind." (Given how cheap this makes individual messages, combined with the efficiency gains from modern communications and the ability to spy on the communications of a populace, I see no reason why a lawful evil society wouldn't have one of these networks.)
- A wizard did it: Telepathic Bond may be made permanent. Every squad of agents should be placed in telepathic bond with their controller "back at base". Given the communications capabilities that this implies, it's the cheapest possible communications network. An "empire" (evil or not) lives and falls on its communications, which means that there should be a correspondingly high priority assigned to this. We can assert, however, that the idea of battle-ready flying squads ready to teleport to help requests may not be part of the repertoire, likely due to infighting and other politics. Still, even presuming that these aren't "always on" (maybe the controller is managing multiple squads) squads should check in when before they expect trouble and after they're clear.
The players get one missed checkin as a grace period, Then a "ministry of divination" (I'm assuming nation-state resources) steps in with a series of spirit planchettes and does a binary search to find the last location of the missing team (as a function of the region that they checked in from). The binary search only needs to be of a region the size that locate object (remember, both a corpse, the corpse's robes, and the identity documents marked with a specific arcane mark are all items) can cover. Happily, the players removed some of the evidence there, but a corpse is still an object.
That binary search takes exactly as long as you wish, as it's a function of the resources invested into the "ministry of divination"'s binary search capabilities and whether or not the "spirits in the area" are favourable to which side. Of course, if I was an lawful evil ministry of divination, I'd make sure that the spirits in the area were particularly well disposed to me: any spiirt that provides a useful answer has their family rewarded with a lowering of quota or other "random" bureaucratic positive outcome. Any spirit that obstructs this will a) have their family harmed, and b) be otherwise removed using normal mid-level adventurer capabilities.
If I was doing this in 3.5, I'd make sure that the communications infrasturcture all had the necrotic cysts implanted in them so that the parent-cyst could scry (and remote take over) any of her agents whenever she desired.
Keeping it down is easy
Dealing continual damage will keep the Big T down for the count as long as you want to keep it down. Drowning him or placing him in an environment that causes continual damage that he can't resist (or something more exotic - Positive Energy Plane?) can do the same job. Big T can't burrow, so you can drop him in a deep hole (dug with magic, probably) and then cave it in on him.
Making Him Dead, Though...
Essentially you'd need a way to strip him of the regeneration trait entirely. 3.5 had a psuedo-poison (Trollbane) that would suppress Big T's regeneration, but that content isn't available in Pathfinder and furthermore their version of the Big T ignores it by virtue of your quoted text. Without a way to strip the ability entirely the best you can really do is kill him, summon a small army of flying things that don't need to breathe, and ask them to drop him off in the vacuum of space.
And Requested By Comment
Further clarification on the Positive Energy Plane was requested, so:
The Tarrasque is not immune to being blown up by the Positive Energy Plane, though it is immune to dying thereby. Dropping him into the Plane is mostly to get rid of him from your dimension; lacking a native way out, he heals, overheals, and then 'dies', returning to 1 hit point to restart the cycle. The Negative Energy Plane isn't as useful because the Tarrasque regenerates the damage it's dealt every round, and even if it comes into contact with some aspect capable of killing it instantly Big T's Fort save is more than sufficient to protect it.
Best Answer
Feather Token (Bird)
Arguably if your target is a living person and that person no longer exists, it won't even try to deliver it. However, if they are in some prison cell it's a fat lot of good sending them, basically, a 'tweet'. Quite a literal tweet in this case. I mean what message would you send? The magic item is specifically an "unerring" delivery, so by strict rule definitions it will deliver it one way or another.
Augury + Seer's Tea = Divination
If you are willing to fork out 500gp, even a Level 3 Cleric can effectively get a spell of Level 7 Cleric. Though hiring a higher level Cleric's services to cast a Level 7 spell wouldn't even cost that much though that is all dependant on you finding a high level Cleric in time. It's a matter of which you find cheaper or easier.
Mark of Blood
This has permanent duration and no range limitation, if you had hit your allied with the benefit of this spell then whoever cast this spell would forever have the ability to know their direction and distance. So it's not so useful by itself unless your GM allows a soft-retcon or it "just so happens" that another NPC had done this to him for whatever reason.
Now, whether you can combine this with the Bird Feather Token... that is something else entirely. You know, hit the bird for 1hp damage (be careful) then try your best to track the bird till the "signal" disappears.
Speak With Dead
Slightly above your level so buying a scroll of this your party cleric (if you have one) could probably make the spellcraft check so you could at least get your the information you need from the Doppelgänger that you killed. They are probably going to know exactly what happened to the person they replicated just to make sure that they aren't seen side by side or whatever.
Nesa's Coin
Another handy item that would have been useful if you'd known about it before but it's too late now. It's not really clear if you can be creative in trying to deliver items.
Good Ole Diplomacy
If your friend is alive yet not free then someone is holding them prisoner, someone is feeding them, someone is probably talking to them. When you get word out of a reward for information about their safe return, well someone is very likely to talk. Hell, even the most hard hearted jailers couldn't at least miss the opportunity for some blackmail and extortion, I mean if their doppelganger master is dead they might as well get some money for it either through ransom or "claiming the reward" for "saving" them.
Keep farming those diplomacy rolls all around taverns to get whatever news you can.
Meta-Analysis of the situation
This isn't meta-gaming, this is your characters thinking "what do I know and what do my enemies know and what do my enemies know that I know?" particularly, your enemies may know a doppelgänger of your friend is being used, do they know the doppelgänger is dead? They know what the doppelgänger should look like... your friend. Do they KNOW you know that?
Is it within the scope of your abilities to then use Disguise spells of some sort to appear as your old friend but then still pretend to be the Doppelgänger. It's the perfect disguise, any spell to detect magical disguise will of course be detected as if should... you are supposed to be a shape-shifter.
You can even walk in acting as if you have tricked your party and are "luring them into a trap".
Would it be possible to go where you'd expect your Doppelgänger to go and wait to be picked up by their contact and work your way back from there. It would be a great counter-play, you'd at least learn a thing or two. Bring up that you need a vital piece of information from the person you (posing as doppelganger) need from the person your are impersonating.