I just realized yesterday that the actor who played Koloth in DS9 is the same actor who played him in TOS. Kudos to them for that. Now, my question is: When did Koloth start looking like a modern Klingon? We know, or have pieced together, that the Klingons in Kirk's time looked the way they did thanks to the use of Human Augment genes to try to enhance the Klingons. This is what caused them to appear to be more human. Thus Koloth's appearance in TOS is explained. However, in DS9, he's got the look of a more modern Klingon, cranial ridges and all. Is this just a mistake on the part of DS9's team, or is there some actual answer for this?
The augment virus depicted in Enterprise had long-lasting effects:
This left millions of Klingons without their ridges, an alteration that was even passed on to their children, though it was hoped that one day gene therapy would be developed to reverse the effects.
From Memory Alpha's article on Koloth:
As a product of 22nd century genetic engineering, Koloth was descended from Klingons affected with the augment virus created in 2154. By the 24th century, he seemed to have been cured or cosmetically altered.
Clearly most of the Klingon population had been cured by the TNG/DS9/VOY era. With a population that again looked Klingon, I could see the being a social stigma attached to those without ridges and elder Klingons either receiving this gene-therapy cure or getting cosmetic ridges.
The decision to give Kang, Kor and Koloth ridges has been controversial among trekkies, particularly because it interfered with the many-race theories which flourished prior to ENT: "Affliction", including those which portrayed Kang, Kor and Koloth as Klingon-Human fusions.
However, in Affliction, we saw that the augment virus could change even fully-grown Klingons (which is a bit weird, but oh well). So, this leaves the door open to these three Klingons havingthe process undone in the apace between their appearances.
As amcintosh suggests, there was a social stigma associated with having a smooth forehead; with being a QuchHa'. In the novel Excelsior: Forged in Fire, the authors describe several attempts to undo the damage. Many of these failed, often with deadly consequences. "The Albino" – the Klingon trio's enemy from DS9: "Blood Oath" – was the result of one failed experiment to reverse the symptoms in utero.
The novel also details how Koloth was provided with a working cure for the virus.