it is claimed that electrons orbit their atom's
nucleus not in well-known fixed orbits, but within "clouds of
probability", i.e., spaces around the nucleus where they can lie with
a probability of 95%, called "orbitals".
I suppose you won't be surprised to hear that your five-minute YouTube video grossly oversimplifies the situation, glosses over most details, and is a bit misleading to boot. It is right, however, that the model of electrons orbiting atomic nuclei like planets orbiting a star does not adequately explain all our observations. The atomic orbital model the video describes is better in this regard, therefore it is probably closer to reality, though it is not 100% correct, either -- it is inadequate for even the simplest of molecules.
But it is important to understand that the atomic orbital model is immensely different from the orbiting electrons model. An "orbital" should not be interpreted as being even superficially similar to an "orbit", other than in its spelling. In particular, the video seems to have given you the idea that an electron in an atomic orbital is at all times at some exact location, but we just don't know exactly where. This seems to be a large part of the inspiration for the question.
A more useful way to look at it is that until and unless localized by observation, an electron is delocalized over the whole universe -- but not uniformly. From that perspective, the density function corresponding to an atomic orbital is not a probability density for the electron's location, but rather a mass and charge density function describing its delocalization. The 95% boundary that the video mentions is in that sense not about where you might find the electron, but about how much of the electron you find.
That 95% number, by the way, is just a convention. It is helpful to choose some boundary in order to think about and depict the location (in a broad sense) of electrons, and that particular number turns out to be convenient for that purpose for a variety of reasons.
It is also claimed that the further away one looks for the electron
from the nucleus, the more this probability decreases, yet it never
reaches 0. The authors of the video conclude that there is a non-zero
probability for an atom to have its electron "on the other side of the
Universe".
It is true that whether you view the atomic orbital density as a probability density or as a mass/charge density, or both, it nowhere drops to exactly zero, even thousands of light years away from the nucleus. But it comes so close that it makes no practical difference.
But more importantly, the question is moot. The atomic orbital model -- which is just a model, remember -- accounts only for a single atom. Even if it were exactly correct for that case, the real universe contains much, much more, at distances far, far less. The atomic orbital model makes no pretense of being applicable at such distance scales in the real universe. If we ever did determine that a particular electron was located at such a distance from a particular nucleus at a particular time, we would conclude that the electron was not bound to that nucleus (and thus that the atomic orbital model did not apply to the pair), because a great many other nuclei, electrons, and other things would interact more strongly with our chosen electron than did our chosen nucleus.
If this is true, then there must be a portion of all atoms on Earth
whose electron lies outside the Milky Way.
Not so. There is a finite number of atoms on Earth, with a finite number of electrons. If we view the electrons as localized entities, so that it makes sense to talk about specific locations, then there is a vast number of configurations of those electrons such that none are outside the Milky Way. Thus, it is not necessary that there be a non-zero proportion of Earth electrons outside the Milky Way.
Which portion of atoms has
this property?
Since this is a probabilistic argument, I suppose you are asking for the expected (in the statistical sense) proportion. Another answer has computed the probability of finding any given Earth electron outside the Milky Way as around e-1032. That would be the expected proportion. To put it a bit into perspective, however, there is on the order of 1050 Earth electrons. If we take the positions of the electrons to be uncorrelated with each other, then the product of those two numbers is the number of Earth electrons we expect to find outside the galaxy.
That would be e50log10 - 1032, which is barely different from e-1032, which is barely different from zero. So, to an extremely good approximation, we expect to see exactly 0 Earth electrons outside the Milky Way. Even if the simplifying assumptions in that computation introduce substantial error, we have many, many orders of magnitude to play with before we noticably move the needle away from zero.