What is the probability for an electron of an atom on Earth to lie outside the galaxy? In this youtube video 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".
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".
If this is true, then there must be a portion of all atoms on Earth whose electron lies outside the Milky Way. Which portion of atoms has this property? 
 A: The quantity you should consider first is the Bohr radius, this tells you an idea of the relevant atomic scales, 
$$
a_0 = 5.29\times 10^{-11} ~{\rm m}
$$
For hydrogen (the most abundant element), in its ground state, the probability of finding an electron beyond a distance $r$ from the center looks something like (for $r \gg a_0$)
$$
P(r) \approx  e^{-2r/a_0}
$$
Now let's plug in some numbers. The virial radius of the Milky Way is around $200 ~{\rm kpc} \approx 6\times 10^{21}~{\rm m}$, so the probability of finding an electron outside the galaxy from an atom on Earth is around
$$
P \sim e^{-10^{32}}
$$ 
that's ... pretty low. But you don't need to go that far to show this effect, the probability that an electron of an atom in your foot is found in your hand is $\sim 10^{-10^{10}}$.
A: 
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.
A: What is said in the video is true, but... remember that the atomic theory is just that: a theory. The theory itself predicts that perturbations will have a really big influence on the results. 
Take into account that the models are based on hypothesis, which are easily violated. For example, spherical symmetry, which allows finding the solution in the hydrogen atom (or more accurately, the Coulomb's potential in QM). Reality is never like that, but we can say that "it is close enough" if the atom is far enough from other objects.
Nevertheless, from here to outside of the milky way there are so many perturbations that the model would just fail. You can say that there's a level $n=1324791$, but there are so many particles out there that the effect of your atom is absolutely beaten by ANY other.
So, does it really make sense to calculate such probability if anything can capture that electron much more easily? I don't think so.
A: The way you phrase your question violates quantum mechanics: saying "there must be a portion of all atoms on Earth whose electron lies outside the Milky Way" is not a statement that makes sense within Quantum Mechanics.  What you can ask, and what others have answered, are variations of the question of how probable it is to find a bound electron at galactic distances from the nucleus it is bound to.
I'm emphasizing this point which we would usually dismiss as semantics because this distinction makes it easier to understand that there is a second way in which your question doesn't make much sense besides as an exercise in the numerics of exponential functions: electrons are indistinguishable.  How do you know that the electron from which the photon of your measurement apparatus scattered is "the" electron belonging to the atom?  The answer is that you can't unless you know that there are no other electrons around.  So you would have to keep your atom in a trap whose vacuum is such that the mean free path length exceeds the radius of your excited atom by several orders of magnitude, which implies that the trap is equally large.  Actually, you wouldn't be able to do the experiment with a trap that is only several orders of magnitude bigger than the galaxy, you would actually need one that is lots and lots of magnitudes bigger.  Why?  Because every other electron in the universe has a non-vanishing probability to be found inside your trap and there are lots and lots of electrons.  You want the total probability of hitting a stray electron to be sufficiently small so as not to perturb your experiment.  Otherwise you cannot assign the electron which scattered your measuring photon to the specific atom that you care about.  After all one doesn't look for an electron in any sense like one would look for a heating cushion.
Edit: I want to add two things which might be of interest if you want to dive deeper into electrons far from the nucleus.
First, you can actually find direct measurements of the electron clouds of hydrogen, see at this stackexchange page: Is there experimental verification of the s, p, d, f orbital shapes?  This shows, never mind the terrible color scheme in the article, the rapid drop of the probabilities at increasing distances.
Second, atoms where the electrons are far from the nucleus are actively researched.  In these so-called Rydberg atoms the electrons are excited to energy levels just below ionization where current experimental setups can get close enough to ionization to reach atomic radii $r \sim \textrm{const.}/\Delta{}E \sim 100 \mu m$ with $\Delta E$ the ionization energy.  That's still a far cry from galactical distances but these experiments show that quantum mechanics actually works a few orders of magnitude closer to the length scales you were interested in.
A: Given a single electron, what is the probability that it is found outside the Milky Way?
We can estimate it using the ground state wave function of the Hydrogen atom,
$$ \psi_{100} = \frac{1}{\sqrt{\pi a_0^3}} e^{-r/a_0} , $$
where $a_0 \approx 5*10^{-11}\, m$ is the Bohr radius.
$|\psi|^2$ is the probability density, integrating gives
$$ p_1 = \int_R^\infty |\psi_{100}|^2 4\pi r^2\, dr = \frac{e^{-2R/a_0}(a_0^2 + 2a_0 R + 2R^2)}{a_0^2} . $$
Plugging in $R \approx 5*10^{20}\, m$ the radius of the Milky Way, we get
$$ p_1 \approx \exp(-2*10^{31}) \approx 10^{-10^{31}} . $$
This number is so small, it is hardly possible to grasp really how small it is.
There are a lot of electrons in the Earth - about $N = 10^{51}$ - but the number of electrons is utterly tiny compared to these odds. The chance that any electron is found outside the milky way is
$$ p = 1 - (1 - p_1)^N \approx N p_1 = 10^{51} \, \cdot \, 10^{-10^{31}} $$
which doesn't even make any dent.
A: I want to tie together some themes that have already been mentioned here, but I want to phrase the ideas differently.
The idea that a hydrogen atom can be described by a one-nucleus one-electron wavefunction, to wit $$ \psi ( r_{nucleus}, r_{electron}) $$ is an approximation that is valid only when the effects of every other atom in the universe can be neglected.  If I have two close interacting hydrogen atoms I need to study a two nucleus, two electron wavefunction $$ \psi ( r_{nucleus 1}, r_{nucleus 2}, r_{electron 1}, r_{electron 2} ) $$ and consider all the quantum mechanical symmetries that apply because all electrons are indistinguishable and are fermions.  Among other things, by studying this second wavefunction I will discover that two hydrogen atoms may sometimes be better described as a di-hydrogen molecule!  Something entirely qualitatively different compared to isolated atoms.  This is a very important result of quantum mechanics and quantum chemistry.
When we consider that any given electron and any given nucleus may be very far apart and that there may be very many other atoms in between them we need to expand our wavefunction to consider all the nuclei and all the electrons. Our solutions may very well not look at all like those of isolated hydrogen atoms.  Most importantly we will lose the ability to definitively associate any given electron with any given nucleus.
As a result of this, the statement that an atom near me now has "its electron" on the other side of the galaxy is not a well-defined statement in quantum mechanics.
However, it is certainly mathematically meaningful to hypothesize a universe with just one nucleus and just one electron and discuss the (remote) probability that, in any given quantum state, they are separated by a galactic scale distance.  Some other answers give these numbers.  But that is not our universe.
