Actually, a less severe (but still quite annoying) method that you might be able to work around for titan loss/recovery is to require you to rebuild the titan construction base once a titan has been constructed there. Those things are not cheap, not incredibly fast builds, and generally a pain. So you can either rebuild the titan construction field right away (and have to worry about cost), wait and hope it doesn't come up soon, or rebuild when they're going- or build a secondary one at another star system, even.
It increases the penalty for losing one without making it crushing, and making it something you can plan around.
Or of course any of the other options where you lose some levels/xp, get a slight damage debuff, etc. Or perhaps a sliding scale where you gain levels (at about the buy level rate) till it's back up to it's full power. I don't think it should be game-losing to lose a titan (since a level 8ish titan vs a level 1 is just not reasonable), but I do think it wouldn't suck to give some sort of penalty beyond build time and cost.