Simple explanation for the plot...

[Ragnar]

Obviously everything that follows is spoilers...
This goes by a duel deterministic assumption, mixed with a Terminator Genisys acceptance that if time travel happens, time travel interacts with other time travel, including time travel that is the result of said time travel.

Original Timeline:

Elysium discovered Deponia's population, thus canceled the destruction.
Rufus fell to his death. Goal saw through Cletus' disguise and mourned, complete with the anger stage of grieving witnessed in the time loops.
Elysium never launched to Utopia. Eventually everyone died given that the planet is not fit for life.
Archaeologists from Utopia learn of the dead planet, in particular the failed plans to colonize Utopia, and decide to view it at peak population...

Unseen Timeline:

Utopian archaeologists explore Deponia. Probably don't so much as step on a butterfly.
The butterfly effect happens anyway, AKA Rufus. Rufus has done strange scientific experiments to himself, including trying to replace his nevus system with molten lead to increase his imagination (built in tinfoil hat effect, AKA remembering former timelines up until death or reset). Unseen Rufus doesn't break Toni's glasses, thus they stay together (imagine a romantic hot air balloon ride, or Rufus blowing them both up... their fate is irrelevant).
Goal discovers Deponia is populated, but her mind is reset to a backup.
Elysium never learns of Deponia's population, and blow it up. They go to Utopia...
Utopian archaeologists are unable to return home, because their future no longer exists (or maybe just their launch point on Deponia no longer exists, due to Mustache Rufus).

Mustache Timeline:

Mustache Rufus is saved mid fall by a variant of Doomsday Goal.
Doomsday Goal dies in his arms, he grows a mustache... Under the influence of the mustache he destroys the planet.
If Fewlocks attack him is irrelevant, what matters is he is a planet destroying madman with a mustache.

Doomsday Timeline:

Rufus wakes up from a nightmare, and sets out to prevent himself from growing a mustache. The Utopians not realizing the horror of mustaches, try to repair time to ensure he grows one. Many lesser loops, and a Doomsday Goal steals the time-ship to rescue her Rufus, but SEE MUSTACHE TIMELINE.

The game of course happens within variants of this, but also dealing with the result of this in itself.

Restored Timeline:

Doomsday Rufus prevents Goal from saving him. Rufus' fall to their deaths. Normal Goal continues as seen in ORIGINAL TIMELINE, until encountering time traveling Rufus later (her main loop happens). Doomsday Goal having gotten to say goodbye moves forward in the grieving process.

The end is the same, but there's been a slight detour in it. We don't get a happily ever after between Goal and Rufus, but we know Cletus' did not get the girl (or at least not for very long), and she moves on in her life and is open to love again (hence her sometimes marriage). Rather than him letting her go to save the world as he did in the previous games, she got the chance to let him go for much the same.

[uanime5]

Why did the Utopian attack on Rufus in Elysium not happen in every Doomsday Timeline? Especially since the Mustache Timeline can't happen without the Utopians following Doomsday Rufus and finding Original Timeline Goal.

Your Mustache Timeline is also wrong as the Doomsday Timeline Rufus has to use McChronical's car to rest time. Without Doomsday Timeline Rufus existing in this time line the Doomsday Timeline Rufus cannot happen.

How did Doomsday Rufus get back into the time pod after falling to Deponia? He's with the Utopians in the dinosaur world after the time pod was destroyed so he had to have survived the fall to Deponia and somehow managed to get back into the time pod.

Also you haven't explained the Goal in Interim Time who had the time pod.

[Ragnar]

Basically blame loops in time, the deterministic limit experienced by some, and Rufus' magic memory. Or to put it another way, "it's like a pizza box that you fold in the middle and then take a pen and..."

Originally posted by uanime5:

Why did the Utopian attack on Rufus in Elysium not happen in every Doomsday Timeline?

They were stranded, turning the time crank every day to repeat it until the thieves returned. Attacking Elysium is part of an advanced loop chain rarely reached. They of course retain no memory between loops, unlike Rufus.

Your Mustache Timeline is also wrong as the Doomsday Timeline Rufus has to use McChronical's car to rest time. Without Doomsday Timeline Rufus existing in this time line the Doomsday Timeline Rufus cannot happen.

I'm unsure what detail you believe me to be mistaken on. Mustache Rufus is the furthest forward Rufus known, but he need not always exist. There's of course variants of him, but the gist is if Goal dies before him, he grows a mustache and destroys the planet.

How did Doomsday Rufus get back into the time pod after falling to Deponia?

The backseat narrator Rufus dragged himself back there, as seen in the game.

...Also you haven't explained the Goal in Interim Time who had the time pod.

What about her? She's a time anomaly where Goal stole the timepod but didn't die, she didn't die because the Utopians destroyed the future using the time crank. When that loop was broken, Doomsday Goal never became her, and instead saved Rufus from the fall, but we all know how that turned out...

[R-OVERMANN]

It's not over. The plot has been left open twice now. Rufus is dead, But i smell deponia spinoff in the future. Goal's story it seems, is not over.