One of the more famous horse-thief songs is the Hungarian "Laszlo Feher", mangled by some American folkie of the 1960s into "Anathea". A few threads about it here - that may be what you're thinking of.

More recently:

Songs of the Neapolitan Camorra

Narcocorrido

and of course quite a lot of rap. Like this rap for Al Qaida, if it's real (I haven't explored that one any further).

A bit more political - how about the Chechen anthem? Here is a video of a group of women singing it. It seems to portray the entire nation as a collective outlaw.