Without looking, can you name all current members still at large on the FBI's Top 10 most wanted list? No googling.
The reason why the list works is because it brings awareness to the fugitive, who may be hiding out in a small town that wouldn't have thought otherwise about their loner neighbor. You wouldn't believe the number of cases America's Most Wanted solved by having some little old lady say "I know him... he mows my lawn for a little extra cash?" or similar.
That said, it really depends on how important was the guy(s) you killed. Presumably if you have long distance communication, the police/military/city guards would have better access to that system, so a reliable source of information could get out. As the joke goes, "How Important do you have to be to go from being a victim of murder to a victim of assassination?" As a general rule, your victims aren't nobodies and if you'd do it enough, you'd be manhunted to hell and back.
I think a more likely scenario is that you're assassin runs afoul of local law enforcement, who are giving him trouble, only to have the local thieves guild show up to help you on the logic of "Enemy of my enemy is an excuse to hurt my enemy. Potential ally is just gravy." After making the get away, probably open the conversation to "What did you do to draw their attention... Want to avoid that when I'm on a job?" and upon learning that he murdered the feudal lord the next town over, all sorts of fun dialog can happen ("Really? The posters said you were 10 feet tall!" "He can't have murdered that lord... they caught that guy... heard he was a dairy farmer." "If he's been caught, then why hang the wanted posters?"). Especially fun if you hear it in the voice of the two pirates or two soldiers from Pirates of the Caribbean.
One final thing: Unless this is a guy so out of his depth in the criminal underworld, he gave himself his own outlaw name ("I'm Starlord" "Who?" "I'm Starlord, man... the famous outlaw?") or was given his name because no one knows who he is beyond a telling clue to his identity or method to his murdering (The Beltway Snipers did have an outlaw name they wanted to be called, but the police and media dubbed them the Beltway Snipers after the pattern of attacks with proximity to the D.C. Beltway and their method of attack emerged. Most famous serial killers are don't operate too far from homes, so they get a rep for a specific location.). To my mind, Jack the Ripper is the only famous criminal who's press name was self given and recognizable. Assassins and serial killers and most other kinds of criminals don't invest much into brand recognition because, well, the most common people to recognize their brands are crooks.