First, let me address why the Marle Paradox is not a Paradox. Second, let me address your theory, FouCapitan, specifically.
MARLE PARADOX
The Marle Paradox is only a problem if one inaccurately pinpoints the event that caused a change to the timeline.
The Paradox assumes that Marle's appearance in 600AD is enough to change time drastically enough in order to Marle to have never existed in 1000AD so that Crono would not have had a reason to travel back to 600AD to even save Marle.
However, such an assumption is contrary to the themes of Chrono Trigger. Time does not change until the actions necessary to change it are taken. The emphasis is placed on the individual taking action.
Crono starting his quest to defeat Lavos does not itself cause Lavos to be defeated. It is only the actual defeat of Lavos that causes time to change. The actual action. Crono's mere presence in the past does not change the future.
We can apply that to the Marle Paradox as well. Marle's mere presence in 600AD must not have been enough to cause a significant change to the timeline that would prevent Crono and Lucca from traveling back in time to save her.
As the reason Marle might cease to exist is that Leene would have never been found (or so the game presents), logically Marle's presence in 600AD did not prevent Leene from being found. She was a poor substitute, so we might assume that shortly the King and others would have realized their mistake and called the search back on.
So even with Marle in 600AD, the key factor that resulted in her non-existence must not have been caused by her.
Next, Crono traveled to 600AD. If his mere existence in the period would have resulted in Marle ceasing to exist, then she would have ceased to exist by the time he got to the castle. Why? Because every time we see time change in the game, that change is immediate. Therefore, Crono's actions up until she disappears could not have caused her to cease to exist.
Whatever the impetus was that caused Marle to disappear, it could not have been from mere presence in 600AD. And whatever caused the disappearance could not have happened until around when she disappeared. Since Lucca shows up right after Marle disappeared, we may reasonably assume Lucca was already in 600AD when that event occurred, which singles that while Lucca stayed in 1000AD, that was a timeline in which Leene had still been found. It was only after she traveled, and subsequently only after she obtained TTI, that Marle ceased to exist.
So while we don't know the action that caused it, we know that all three of them were in 600AD whenever the action that destroyed Marle occurred.
But that only addresses half the paradox. TTI should have protected Marle from the changes that destroyed her, shouldn't it?
Maybe.
For one, her transportation to 600AD was non-standard. It may be that TTI was not granted to her because of that (maybe only certain modes of time travel grant TTI).
For another, TTI only protects one's appearance in a time period, not one's actions there or indeed one's continued existence. While TTI seems to preserve the memories of Crono & Co, this is the only time that we see someone cease to exist because of an action. These are concepts on a different scale. The matter that comprised Marle, having never formed Marle, might have been needed elsewhere, as it were (for different people, plants, animals, etc) and thus Marle had to be destroyed in order to preserve the conservation of mass/energy. The conservation overruled any protection that TTI might bestow.
As we never see another situation where these two concepts come into conflict, we can't know. However, there are plenty of possible explanations. Until such time as more evidence comes in regarding the matter (unlikely), it does not make sense to throw out TTI just because we don't know which answer to the Marle Paradox is the right answer (as there are answers).
FouCapitan's Theory
To note (it seems like I have to harp on this), at no point in the game is it stated that the Entity actively attempts to have Crono & Co defeat Lavos. That is their goal; all we are told of the Entity is that it wants to relive its memories and share them. This is important because you essentially replace Time Traveler Immunity with "The Entity Did It," except we have no firm reason to suppose that the Entity even had a desire to do it.
TTI preserves one's appearance in a time period, nothing more or less. Melchior at the Fair doesn't recognize Crono and Marle because he is the original Melchior, send to 1000 from the original Ocean Palace Incident which did not include them. Whatever changes Magus, Crono, and the others make in Zeal, 1000 AD Melchior won’t know about them because his memories are those of the original Melchior. Any changes that occur to 1000AD, however, he would be aware of, because after he appeared, he would have lived in a world with those changes. Only his appearance, not the subsequent actions, are protected.
@Eske
Marle doesn't disappear when Ayla leaves the past because, once again, time does not change until the actions are made that will change it.
Let us say that Ayla in the game is 25. Then let us say that she will have a child when she is 30 that is Marle's ancestor. Therefore, until Ayla is 30, she cannot not sorry, the double negative is needed have the child, so Marle's can't cease to exist because Ayla isn't in the past until Ayla is 30.
Just as mere presence in a timeline can't change time, mere absences can't change it either.
I'll have to take a look at your thread(s) (I've been lax in participating in the analysis forum for a few months). From what has been said here, I think you're explaining something I've been trying to convince people of since septemberish 2007. As such, I'm very interested in what you have to say on your matter.