Culture penalties stem from the population increasing with different culture's buildings in that town.
If you exterminate a populace and let it grow again with the foreign culture's buildings in place, it seems that you will still have the cultural penalties.
If you reduce the population and destroy the foreign cultures buildings, you will grow a nice happy loyal population.

Carth, the first building I replace in a conquered settlement is the temple. I usually destroy all foreign culture's buildings straight away (apart from any I need to retrain my soldiers). Then build from scratch.