Let me explain,
My main idea is that when a player kills another player a small reward is added, but if he kills a player of more importance than his reward increases, or if he steals from stores and is seen or something, a reward is added. .
They could also put next to the market tab a page of the people with a reward for their head, and be able to buy a GPS style to know where they are, but not their exact location, if not, their region
We had head bounties at some point, basically it got abused and so CCP removed it, But did NOT return the bounties to the people who placed them, Grrrr. (thats right CCP - Our memories are longer than your sniff of disdain… dont get me talking about 10th Anniversary Mystery Codes or we will be here all day).
Also there are ‘Locator Agents’ can find people like u suggested.