Lavos Paradox (Reasons for)

Inquiry

We know that once a person has time traveled, he or she is protected from his or her changes to history and always emerges at the point of arrival on the timeline (Time Traveler's Immunity). We also know that Lavos seemingly exists in a Pocket Dimension, as defeating the shell in 1999 A.D. makes the shell disappear in 12000 B.C. However, Lavos's behavior interferes with these principles. Chrono Trigger and Chrono Cross suggest that Lavos was defeated in 12000 B.C. when the party went to the Black Omen. This is evidenced by the Black Omen's need to be destroyed to fully complete the game and its inability to be destroyed in 1999 A.D. A Chronopolis quote also notes that no information can be gathered on Lavos in the current timeline as Crono and his friends prevented him from existing:

~~~~ -- LAVOS -- ~~~~
   ~
   ~~~~~~~~~~~~~~~
   An extraterrestrial life-form
   that is thought to have
   fallen from the heavens
   65 million years ago.
   On the time line that existed
   before history was changed,
   Lavos was assumed to have
   slept deep below the planet's
   surface...
   Sleeping and consuming the
   planet's energy up until the
   day of destruction known as
   the '"Apocalypse."'
   There are those who believe
   that, 12 thousand years ago,
   the legendary ancient magical
   civilization known as Zeal
   came into contact with Lavos.
   That fateful encounter is
   said to have resulted in
   Zeal disappearing from the
   surface of the planet within
   the space of a single night.
   However, the very existence
   of the ancient civilization
   of Zeal has never been proven,
   so up till this day this
   theory cannot be confirmed.
   On some time lines, Lavos
   appeared on the surface of
   the planet in the year 1999
   and brought the world to
   ruins.
   However, a group of young
   time travelers saw where
   their planet's history was
   heading and, through their
   actions, rewrote time.
   This very research facility
   exists on that new time line...
   In a world where, thanks to
   the defeat of Lavos by the
   young adventurers, the
   Apocalypse never happened...
   On a temporal vector where
   human civilization continued
   to evolve unhampered.
   All the data on Lavos that was
   obtained from tracing different
   parallel world possibilities
   has proven to be volatile, with
   fluctuating discrepencies.
   Perhaps, at this point in time,
   it is nearly impossible to
   obtain any true information
   about Lavos.

Now, remember that in 2300 A.D., Crono observes Lavos coming out of the ground to destroy the world. This establishes that Lavos as having Time Traveler's Immunity, as exiting a Pocket Dimension would grant the creature that status. Since Zeal falls on all timelines after Chrono Trigger, we know this to be true (otherwise Lavos would not emerge from his Pocket Dimension and destroy Zeal at the Ocean Palace disaster after his defeat). With this in mind, consider what would happen even if Lavos were defeated in 12000 B.C. He would still erupt in 1999 A.D., as his existence there is protected by Time Traveler's Immunity! Lavos's actions are incongruent with the principles of time and dimensional travel; otherwise, the future would be destroyed regardless of the point of Lavos's defeat. Only if Lavos were defeated in 1999 A.D. would this be remedied, and we know that he was defeated in 12000 B.C. Are there any possible solutions for this problem?