Telepod Paradox (Reasons for)
If Marle changes history when she goes back in time, how do Crono and Lucca still travel to 600 A.D. from their home version of 1000 A.D.? The rest of the series dictates that as soon as changes are made to the past, the future changes resultingly in an instant. If Marle went back in time and significantly disrupted the Guardia history, 1000 A.D. would change; the Mystic War may not have been won, or the royal family may have simply changed bloodlines. In any event, the same 1000 A.D. would not exist as it was known to Crono and Lucca, yet they are still able to pursue Marle in time. How is this possible? Conceivably, another Crono and Lucca could find their way through time in an alternative timeline created by Marle's disruption in the past, but this Crono and Lucca would have no recollection of Marle. Despite applicable theories, this is probably a plot hole with no intended workaround by the creators.
Eriol, GrayLensman, Leebot
Leene is found despite Marle's introduction to the era anyway, meaning history is preserved normally (provided Marle doesn't muck around too much and dies peacefully of old age) until the modern era. This would allow the same 1000 A.D. to roughly exist. The only problem here is that Marle is said to have disappeared (see Marle Paradox). Even if she did, her disappearance would have served as motivation for the soldiers to find the real Leene, which resolves that loose end. If this is the case (with Leene surviving; note that Frog was on his way to rescue her anyway), we have the following series of events:
1. When Marle initially time travels to 600 AD, her presence in the past results in a new timeline being formed, sending the original timeline to the DBT.
2. In 1000 AD, Crono and Lucca are instantaneously discared and replaced by new versions of themselves. Since they still exist and remember Marle time traveled, in this timeline the Guardia royal line was not interrupted.
3. When Crono traveled through the warp, another timeline was created in which both Crono and Marle exist in the past. In 1000 AD, another new version of Lucca is created. Since Lucca still exists and remembers Marle and Crono time traveling, the Guardia royal line was not interrupted in this timeline either.
4. After Lucca constructs the Gate Key, she follows after Crono and Marle, creating another new timeline consisting of the events witnessed in the game. Queen Leene doesn't die because Crono saves her. Marle disappears, supposedly because she doesn't exist in the timeline. The future version of Marle may or may not exist.
5. Once Lucca, Marle and Crono return to 1000 AD, the timeline is not noticably changed from the original. If the new version of Marle didn't exist in the previous timeline, she does now.
The effects of Crono and Lucca's actions immediately and instantaniously affect the timeline when they emerge in 600 AD. The future doesn't change as they act, except when time traveling. From the perspective of 1000 AD, all of the time travelers actions have already occured once they emerge in 600 AD.
Super Warp Protection
This theory assumes that Marle caused a significant disruption in 600 A.D. that would alter the future. When Lucca built the Telepod, she most likely tested it herself. Crono then used it at the Millennial Fair, and Marle finally used it to go to 600 A.D. Now, if the Telepod's warping is considered a form of time travel or dimensional distortion, then Time Traveler's Immunity may be invoked for Crono, Marle, and Lucca. This would take care of their preservation as individuals who know about Marle up until her disappearance into the past. The only problem remaining then is that the state of the Millennial Fair does not change either. It is a stretch, but perhaps Marle's disruption did not significantly affect history, and events played out mostly the same to result in a Millennial Fair at that time.
Temporal Revision Theory
What if Crono made it in the Gate before the actual Gate spit Marle out in 600 A.D.? Though this is possible, it would not help Lucca's case, as she still came in after Crono and Marle were both in the past and history was changed.