Normally I would use the name to be sure, since that's what people tell you. "BearHoldingAShark the Goblin stole my baby." You go find a goblin named BearHoldingAShark.
That said, this is a good suggestion for expansion. For instance, I should at least be able to ask people, "Who's your leader?" and have them tell me, "We've been following BiscuitDoughHandsMan ever since he bested BearHoldingAShark and took over," and then you know that while BearHoldingAShark has doubtless been snuffed these are still his bandit party and there's still justice to be dealt out.
I'd also say that lines like "I'm on an important mission" shouldn't just be spat out merely because the character has an objective currently, they should be tailored to whatever they want you to believe they're up to (which may be just a cover story, or may really be what they're up to). Killing everyone in town for kicks and giggles isn't an important mission in any normal sense of the words, and so if they tell you they're on an important mission they should be able to tell you it's because they're here defending the town from some bandits who happened by (even if in reality they *are* the bandits and are *not* defending the town). Maybe, say, make it possible to ask characters to elaborate on certain responses like that: "Why are you travelling?" "I'm on an important mission." "Can you speak of this mission? What is it that you seek?" "[explanation here]"
And, on another angle of hunting ruffians, it should be possible to ask the people who tell you about them for more info to help recognize them. "BearHoldingAShark has a great scar over his left eye. He always boasts of the time he won the family pie-sitting contest in Free Country USA." "Everyone in the gang wears a bandana on his left upper arm." "He has with him two goblins, two humans and an elf." "He is a giant of a man, dressed in red, who carries a gigantic weapon and has a mohawk." I'd want that kind of info if I was really tracking someone, not just ways to interrogate suspects without them realizing I'm trying to find out if they're the murderer's I'm after (although I'd like that too). And it would probably be inaccurate from time to time too, due to being out of date (BearHoldAShark decides to ditch the humans for some reason, the bandana insignia gets swapped out for tophats), due to simple dishonesty (one of the members of the gang posed as a commoner to lie about the gang to throw off the trail of justice, and the rumour you later heard came from that lie) or due to simple confusion (turns out that even with that info there are still three guys in the neighborhood dressed in red and carrying gigantic weapons, and other rumours don't match the part about a mohawk), but by and large it should be possible to use the information and when it's not accurate to get a pretty good idea of why it wasn't.