On the scale of the galaxy, starships are specks. On the scale of trillions, one or ten or a hundred time travellers is as near to zero as makes no difference.
I feel like you haven't quite thought through the maths of what random means in this context.How many times can any (effective) group randomly travel through time?
If time travel is rare and random, then let's call the chance that a group capable of effecting change gets randomly transported to the time and place they need to be to effect that change P1. P1 is small, because as we've established, time travel is rare, groups capable of effecting change are a minority, and the window of time and space they need to land in to effect that change is vanishingly small compared to all the other times and places they could randomly arrive. Nevertheless, P1 > 0.
If the event they are trying to avert is going to keep trying to happen, with a probability P2, then what is the probability that they can fix it this way every time? It's P1^N, where N is the number of times they have to intervene. Meanwhile, the chance that the event doesn't eventually happen without their intervention is (1-P2)^N. Both of these probabilities get exponentially smaller as N gets larger. As N -> infinity, they go to zero.
Your problem only arises if P1 = 1 - i.e. if time travel is not random and rare, but people can do it at will.
In the most 40K terms possible, you're asking 'why doesn't the galaxy just roll a 6'.
That is... not what those things are. The concept of fate and prophecy and predestination in literature don't boil down to a 21st century consumerist catchphrase for not spoiling the ending of a movie.That's literally why spoiler alerts exist.