Why doesn't the phase diagram of water look different? How can sublimation occur at much lower temperatures than 0 degrees celsius provided that the pressure is sufficiently low? The melting point of water is relatively unaffected by the external pressure compared to the boiling point. Therefore it seems reasonable to assume that below 0 the molecules wouldn't have enough kinetic energy to overcome the binding forces in ice no matter how low the external pressure is. 
If the boiling point is below the melting point, shouldn't sublimate happen at the melting point (which is at a higher temperature)?
My question is: Why does the phase diagram of water look like this

and not like this

 A: Your first misconception is the thing about kinetic energy of particles: Particle energies follow a distribution that does not have a cutoff. I.e. there will always be particles present with enough energy to go into the gaseous phase. If you lower the temperature, the count of these particles decreases, but it never reaches zero. Consequently, you get sublimation whenever you have an ice surface exposed to perfect vacuum. The count of sufficiently energetic particles dictates the maximum rate of the sublimation, and there is always a vapor pressure at which this rate of sublimation equals the rate at which gaseous particles hit the ice, dissipate their energy, and enter its phase.
The melting point is largely invariant of pressure because melting/freezing does not change volume much. Volume grows a bit when freezing at room temperatures, so very high pressures can discourage water from entering the solid state, lowering the melting point a bit.
Of course, the same volume dependency is present with the gaseous phase: Water takes much more space when it's low-pressure vapor than when it's solid or fluid. As such, it's natural that both the sublimation and the boiling point show a strong pressure dependence: The more pressure, the more energy (= temperature) you need to put a particle into the gaseous phase. The volume dependency between vapor and other phases is much, much stronger at the triple point than the volume dependency between solid and fluid phases, so you have to expect the sublimation point to qualitatively continue the path of the boiling point to lower temperatures and pressures. There is a slight angle between the two curves at the triple point, though, as far as I remember.
A: It is fundamentally related to the probabilistic/statistical nature of thermal motion. Actually, the material will be subliming at any temperature above absolute zero - it's just that the rate decreases exponentially (or faster) with falling temperature, and at that line is where the sublimation is happening fast enough that further addition of heat does not raise the temperature, just cause further sublimation.
At any given time, a molecule has a nonzero probability to have any energy - even very high energies. The reason for this is the randomness of the molecular motions: if you have a bunch of balls jiggling around in any and all ways possible, there's always a chance that for any given ball, its neighboring balls will happen to jiggle all in unison, giving it a coordinated, strong "kick" that ejects it from the bunch. That's exactly what happens here. As a result, molecules gradually leave the material, and it sublimes.
And yes, this would theoretically mean that comets, etc. should disappear eventually, but the timescale required is phenomenal (larger than the elapsed age of the Universe, at the ~3 K temperature of interstellar space) due to the exponential suppression: roughly speaking, at half the average energy, you need twice the balls to all coordinate their "kicks", and that means the probability is squared - first, you have to "roll the dice" right to get the first set of balls to shove, then you have to make a second roll to get the second set to shove in tandem. If the first roll has probability $p$ to "win", then both the first and second together require probability $p^2$. Of course, this is not exact due to various correlating and geometric/dynamical effects, but it still gives you the general idea.
The vacuum sublimation rate at a given temperature has been known for a while and is pertinent especially when it comes to spacecraft design because it means the spacecraft materials do in fact evaporate with time: the rate is given by the Langmuir equation, see, e.g. [1]
$$r_\mathrm{escape} = \frac{P_V}{k_L} \sqrt{\frac{m}{T}}$$
where $P_V$ is the vapor pressure at the given temperature, $m$ is the molecular weight, $T$ is temperature and $k_L$ is the Langmuir constant, $17.14\ \mathrm{\frac{Torr \cdot cm^2 \cdot s}{g \cdot \sqrt{\frac{K}{amu}}}}$, I believe for the units (this is an old paper from 1971! and does not say what unit is used for molecular weight especially). The $P_V$ is exponentially decaying in the reciprocal temperature $\frac{1}{T}$, hence what I said earlier. For water in particular,
$$P_V \approx \exp\left(20.386 - \frac{5132\ \mathrm{K}}{T}\right)\ \mathrm{Torr}$$
so at $T = 3\ \mathrm{K}$ this is on the order of $10^{-734}\ \mathrm{Torr}$, and the evaporation time is thus going to likewise also be on the order of $10^{734}\ \mathrm{s}$, against the generally accepted age of the Universe of about $4.35 \times 10^{17}\ \mathrm{s}$ (Planck Surveyor data). IOW, comets are essentially stable (in fact, they would be more likely [though this is completely speculative as of this writing] to evaporate via more fundamental physical processes like proton decay before they evaporate this way! And that's not taking that the Universe is cooling as it expands.).
A: It's been like 10 years ago since I finished university. It's so long ago I don't remember that much what I learned. I believe that once in either high school or university chemistry or on some web page on the internet, I learned that rarely and occasional, a molecule gets a jolt from surrounding molecules to move fast enough to break away from the surface. It's probably the chaotic nature of their movement. Here is my explanation of what chaos theory is. I believe that there is a continuous velocity field on the surface of a 4-dimensional sphere that has the property that the tinest change in starting position in one direction perpendicular to the direction of travel will grow exponentially and a tiny change in another direction perpendicular to the direction of travel will decay exponentially.
