I think 4-LOM (man, how I have always hated that name!) is actually a proticol droid, or at least he has a proticol droids body. So I think it is safe to assume he was modified to be a bounty hunter. Not sure when the IG model droids were originally called assassin droids, they have just always kind of been that to me. I suppose you are right though, it probably is an invention of the EU (though if this is the case, a very early one, as me an my friends knew him to be an assassin droid since back in the eighties).

Regardless, I don't find the broken down assassin droid in a Cloud City junk heap to be anything unusual in the slightest. Cloud City has always struck me as a rather shady short of a place. The SW universe is a rather grim place, its residence being required to do what they must to survive in a world ran by tyranny. We are introduced to this in the first film through big talking Han Solo and his bragging about being able to out run Imperial Crusiers, his killing of Greedo, and the conversation about him dumping Jabba's "spice" shipment before being boarded. This doesn't strike me as the kind of place were a man like Lando really turns over a new leaf and becomes completely respectable. I have a feeling there is more to the place than a bunch of miners wearing silly clothes. I bet there are more than a handful of people living in that city who know EXACTLY what to do with an assassin droid.