The Old Gods are immortal more in the sense that they aren't and never were mortal, physical destruction of an Old God seems to a pretty ineffective method of "killing" them. It seems that the only way to destroy an Old God completely is to obliterate their essence - something which may or may not be possible (the Old Gods, to me, seem to be the very avatars of the elemental force of Corruption). As long as Corruption exists as a concept so might the Old Gods, even if their forms are destroyed and their essence dispersed. I think that the perverse plans of the Old Gods actually *hinge* on our wholesale destruction of their physical forms and intermediaries, I think the Titans made the same mistake we do in thinking of them as purely physical lifeforms - they imprisoned them physically in various places, but in slaying them we effectively release them from their prisons and allow them to get on with the job of infecting nigh everything in existence.