Generally in troublesom areas, such as Eygpt, I keep the temple, as while the culture penalty will be big, the threat of civil revolt during the time to upgrade your temple to a satasfactory level will be much greater than actually keeping the temple. Also I never replace a temple if it gives me a bonus I want, such as Food +1, exp upgrade, etc.
Basically, small settlements replace, large ones, or temples you want to keep, keep.
And I shall go Softly into the Night Taking my Dreams As will You