What prevents semiconductors working below -40°C or so?
Damage to an IC package at low temperatures while unpowered would be due to mechanical effects; differences in thermal expansion coefficients between the epoxy, lead-frame, and die.
Problems with operation would be due to increased resistance (semiconductors' temperature coefficient of resistance is negative).  When the temperature and doping concentration is low enough, semiconductors will essentially become insulators and not conduct at all, causing unspecified operation.
Some ICs will operate just fine at cryogenic temperatures but they must start up warm to allow bandgap voltage references to boot.
In theory if some transistor &quot;fails&quot; due to carrier freezeout, the IC could damage itself elsewhere (not very likely, as most failure modes are thermal, and everything on the die is very tightly coupled.)
See the tutorial pages here for more.
Edit:
As you note, most devices are characterized between usually -40 °C to +85 °C.  Nothing says they will not work down to cryogenic temperatures.