Yeah I think it would really allow high level players a chance to do more than hack and slash in mass battles.
There would be a bit of detective work and a bit hunting.
Also people could form group to take out bands of criminals.
I believe there should be some Unlawful towns where you could hide out as a criminal but, if your know well enough anyone may be your enemy. So perhaps no place would be safe. A real Gun slinger mentallty.
If you wanted to get real fancy you could ask NPCs if they have seen these people.
At some places NPCs would just give up info other locations you would have to pay to get info.
Charisma rolls could be a factor here.
This idea could have many layers making it really rich.
If you wanted to you could get real complex with this or keep it simple and it would still inspire a lot of new game play.