You can't make them like "If the king sits on a golden throne, you will be attacked by a hydra" as hydras might be extinct by the time it happens - any specific type of creature could be extinct. You could off course make the game create a new hydra but that would be an ugly solution IMO? Unless gods can create a brand new hydra out of nothing.
Another option could be to load the RNG dice so that worldgen never allows hydras to go extinct until the prophecy is fulfilled. To prevent the player themselves making them extinct to break the prophecy, rig things so that the player is somehow unable to discover/find the last hydra (if they get whittled down that much).
For conditional prophecies this would be less ideal of a solution though, because then for every prophecy you have to ensure some required conditions never change (keeping hydras non-extinct is one thing, but how many prophecies about different beasts and kingoms can you keep going?).
In general, rigging RNG so that prophecies get fulfilled is the way to go I think, along with allowing them to be sufficiently vague. There could also be a distinction between prophecies just based on the gods will/promises (like IndigoFenix suggests), and "true" prophecies based on fate itself (some worlds may not even have real "fate").
It's an interesting thought, but it gets tricky in a procedural game like DF. At what point does your failed attempts to overcome an obstacle stop being "fate" and start being "overt magic"? If a prophecy states that the Dark Lord can only be slain by the Chosen Hero, but I decide to attack with an overwhelmingly powerful force, there's a limit to how many times he can repel the attack before you've broken the simulation and created an overly gamey situation where stuff happens "because destiny says so".
With a sufficiently heavy-handed version of fate in some mythgens, "because destiny says so" may not be such a bad thing. I could see a situation inspired by the likes of Leibniz's idea of how interaction between the mind and body worked; his answer was "they don't, God just arranged in advance that they would coincide/act in harmony", so the appearance that "your desire to eat caused your body to move and get food" was really just an illusion, because the mind/desire really didn't do anything.
So maybe fate demands that the Dark Lord gets a snack and then is stabbed, and non-fated things like "desire to eat" or "presence of a stabber" are irrelevant; he will walk to the kitchens against his will and then have a stab wound appear, inflicted by fate itself, because "technically" the knife was never the thing stabbing him, or anyone else, the gods just pre-ordain that people are stabbed, and usually that also a knife happens to be put into the body, and this time they skipped the knife.
It's wouldn't fit all worlds due to the weirdness of this metaphysical system, but it's one option for some. And for the flipside of it, maybe the Dark Lord is immortal
because he is fated to only be killed by one man in particular, and maybe he even knows this and abuses it to his advantage.
You could also try a variety of methods to make his apparent invincibility more "organic" in some other worlds, like ensuring different things always happen to foil attempts to slay him, like a "random" dragon attack decimating an army that he otherwise couldn't have plausibly beaten, or maybe the player sends the wrong person to slay him, and they turn out to be a traitor.
Really, the main thing that would be hard to make organic is keeping him alive if he visits the players fort on the loaded embark area, or if you go after him in adventure mode; anything "offscreen" can be sorted by cheating with the RNG in varying ways.
You could also in some cases go for "you just broke the prophecy and in doing so destroyed fate itself, and now the world is unraveling and being assailed by eldritch horrors, thanks a lot".