My own personal theory is that conciousness would be immune to the effects of time travel - you'd remember the new timeline as well as the old one you destroyed. But that's just my pet theory.

On to a real one, the Quantuum branching theory of time (I can't remember it's actual name, but that name is pretty descriptive of what it is) clears up every single paradox problem; however, it does create one. Under this theory of time, it doesn't matter how complex and impossible a paradox sounds, it's doable. The idea is that whenever there is a quantuum possibility, the universe splits into two universes where each possibility is played out. So, they get thrown into the future of their timeline and see the world destroyed. Through all their meddling in the past, they've made new splits in the universe and through that made a new future without Lavos destroying the world. And since they're technically from another universe, rather than the new, saved universe, they still have full memory of the desolate future.

I personally don't like this theory, but it is an actual theory; and several times during Chrono Cross it looks to me like they're alluding to it, so I think it may be the one they use for how time works in their world. The one problem it does create, though, is that under this theory Marle wouldn't have disappeared when Leene was never found.