Bounties and bounty hunters were around in the Middle Ages as per my quick research in Google.
It would be a very fun thing to add both in fort and adventure mode. Also an endless source of starting weird chain of violent events.
System is:
Some character roles are able to place bounties on characters they thing did bad stuff.
This would be site rulers and lawmakers, like judges and sheriffs etc. I think all sites, also bandit camps, should be able to do it.
Bounties would be placed on thieves and murderers and so on. In adv mode, you'd get one placed on you if you steal stuff and kill people at a site. The worse the crimes, the bigger the bountry, thus hunters would be more frequent and more bad-ass the more bad stuff you did.
The bounty hunters is taken from the pool of adventurers in the world, the people that now are doing the search missions for lost artefacts.
Adventure Mode:
You can both take bounty hunting missions, hunting for the guy, as well you can be the object of bounties.
If a bountry is placed on you, you'd regularly be attacked by bounty hunters. (They should be made stronger for strong characters, as a trained character would just slaughter the standard npc adventurers.) I guess eventally you should be able to redeem yourself of crimes, but as for now I guess you'd just have to deal with them for as long as the character lives.
Fort mode:
You can put bounties on characters that have been to the fort. Alive-bounties would be usefull if you want to question somebody that left about crimes. The bounty hunter will then bring the guy and place him in the jail, and then collect the reward from the sheriff.
Dead-bounties should be for criminals or invaders or monsters (like a were-creature that shows up and leaves the map).
It should also be possible to put bounties on totally random characters for fun, like on the Elven diplomat or some visitor that left - the same way you can convict random characters for crimes. I think this would be hugely fun, and also a way to get the fort into trouble. Like you put a bounty on the wife of the king in a civ for fun - they're not going to like that.
As well, bounties can be placed on your dwarves, say because you send them on a raid and they're spotted stealing stuff.
It should also be possible for it to happen if a dwarf tantrums and kills some outsider. His people could then place a bounty on the tantrumming dwarf, and some day a hunter then might show up looking for him/her. In general, agression by your dwarves against people from other sites, like killing merchants or visitors should be able to trigger a bounty on the dwarf that did it.