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.).