Yet on a phase diagram sublimation never begins [highlight mine] until well above absolute zero.
At (theoretical) absolute zero substances lack the energy to undergo a phase transition. The structure is a perfect lattice and the only energy is zero-point energy.
In addition, points on phase diagrams represent equilibrium points. A solid in a vacuum is in non-equilibrium. Vapor pressure is a value associated with an equilibrium state without beginning or end.
Only abovewhen T>0 K will molecules have sufficient energy to form a disordered phase or detach from a lattice. A disordered interfacial phase on a solid surface does not represent a minimum free energy state relative to (a perfect) vacuum. Surface molecules with enough energy will tend to detach and escape into a persistent vacuum. Note they will tend to take energy resulting in evaporative cooling. A similar principle is used to generate super-cold atoms, see for instance this Scientific American article:
Further cooling is done by evaporative cooling, by selective removal of the most energetic atoms from the system. The same process cools a cup of coffee when the most energetic molecules escape as steam, thus lowering the average energy and therefore the temperature of the remaining molecules. In a magnetic trap, the most energetic atoms can move farther against the pull of the magnetic forces, and can therefore reach regions with higher magnetic fields than the colder atoms can. At those high magnetic fields, they get into resonance with radio waves or microwaves, which changes the magnetic moment in such a way that the atoms fly away and escape from the trap. Nice animations of the cooling procedure can be found at http://www.colorado.edu/physics/2000/bec/temperature.html [ [ Source: How are temperatures close to absolute zero achieved and measured? Scientific American, Jan 19, 2004 ]