Just like how Ramethus could not be killed, for he was conflict and strife and strength born of hardship, and to raise arms against him was to feed him.
The Solars then murdered him.
I can personally attest, based on discussion in another thread, that the Vodak is one of the idea-tumors you should be cutting off of your Creation and incinerating as a matter of course. It's a boring, ridiculously contrived raid boss whose special snowflake immortality only exists to force players to follow the railroad tracks its module lays down for them.
To be specific, the way you kill it is by pulling a lever to activate a First Age Wonder that magically autokills it, even though the module also says the gathered might of the High First Age couldn't put a dent in it and they were forced to simply cede a section of land to the thing. While also building a magic Kryptonite ray that can instakill it, of course, but not actually bothering to use it.
Truly, a narrative tour de force that justifies ignoring one of the setting's most basic elements.
The primordials were invincible, just like humans are invincible. Which is to say they are not really that invincible. A ant might think a human is invincible, but it still can be killed. A human might think it can't be killed by something like an ant, but enough ants can still kill you.
That description you made is hyperbole, like how the primordials were invincible. It's like saying that 1 mote has the power of an atomic bomb, or that the Eye of Autocthon is omnipotent. An exaggeration that was probably intended to convey a sense of grandness.
Sometimes stuff is meant literally, and If we are talking about core parts of the setting, Arguably one of them is how defenses work.
Someone using "Seven Shadows Evasion" could dodge the earth while falling yet still land*. A primordial or the Incarna can't just say no it hits, despite how much greater they might be. You can't "just" ignore these defenses thingies, they have to be worked around.
You can make some sorts of analgies about this like:
A hero whose power comes from his determination can fight the makers of the world. When they shatter the faith in his goals, he finds he can longer match them.
A god returns even if you destroy his body, as his spirit still lingers. So you eat his soul.
If we are talking about plot tumors or whatever, In the case of that tree behemoth it doesn't really apply.
It isn't impossible to destroy every tree in Creation, but it is rather hard. The thing is that Elysande, isn't something like a death lord who is going to blow up a city or the country. It is a tree that sits around and gives a small amount of healing fruit, and it can't actually fight.
In addition you can still get rid of it. The tree thing regrows from a seed that has to be planted first. You can just keep the seed in glass jar and forget about it.
I don't think that lever device showed up in 2e. The Vodak takes 100 years to come back though.
*Technically you can not dodge or parry falling in 2/2.5, even with charms. Which is stupid.