I will not answer your question directly; only give you some tools that should help you answer the question (in practice) yourself.
To focus the attention, find below a typical heating/cooling diagram for a frozen pure substance.
The vertical axis marked $T$ represents temperature (in degrees Celsius).
Three significant temperatures are indicated on the $T$ axis:
$T_c$: this is the temperature of the cold pack while in your freezer.
$T_f$: this is the melting (fusion) point of the material in the pack.
$T_H$: this is the temperature after the pack has been carrying out its function for some time. Often it will be room temperature.
The horizontal axis marked $H$ represents Enthalpy. Enthalpy is what is known in physics as Heat Energy. $H_1$, $H_2$ etc are various heat energy contents of the pack as it slowly heats up from $T_c$ to $T_H$.
You’re quite correct that the best pack (there are other, practical criteria, of course) would be the one that on heating would extract the highest amount of Enthalpy from its surroundings (typically a cooled picnic box or such like) to heat up from $T_c$ to $T_H$. So let’s analyse this.
The overall Enthalpy the pack has to absorb is simply $\Delta H = H_4 - H_1$. We can calculate this as follows.
The heating diagram is divided in three areas marked $I$, $II$ and $III$.
Area $I$: the frozen pack is heated from $T_c$ to $T_f$. The Enthalpy change for area $I$ is given by:
$\Delta H_I=mC_s(T_f – T_c)$ where $m$ is the mass (in $kg$) of the pack and $C_s$ is the specific heat capacity of the solid pack material (in $J kg^{-1} K^{-1}$).
Area $II$: in this area the pack is melting (during melting $T$ stays constant at $T_f$). The Enthalpy change for area $II$ is given by:
$\Delta H_{II}=mL_f$, with $L_f$ the latent heat of fusion (in $J kg^{-1}$). For melting $L_f$ is a positive value.
Area $III$: the molten pack is heated from $T_f$ to $T_H$. The Enthalpy change for area $III$ is given by:
$\Delta H_{III}= mC_l(T_H – T_f)$ where $C_l$ is the specific heat capacity of the liquid pack material (in $J kg^{-1} K^{-1}$).
We can now add it all up:
$\Delta H =\Delta H_I + \Delta H_{II} + \Delta H_{III}$.
Or:
$\Delta H = m[C_s(T_f – T_c) + L_f + C_l(T_H – T_f)]$
We can now conclude a few things, in order to maximise $\Delta H$:
- High mass $m$ is desirable.
- Large difference $T_H-T_c$ is desirable.
- Both $C_s$ and $C_l$ should be as large as possible.
- Large value of $L_f$ also increases $\Delta H$.
This general treatment was for a pack filled with a single pure substance but can as an approximation also be used for mixtures of substances, by adjusting the masses, latent heats and specific heat capacities.
A couple of decades ago I was peripherally involved with some research on the properties of ice cream being done by the company Walls in the UK. The work was on relating the consistency of the ice cream to the microstructure, so it was quite closely related to your question.
Anyhow, ice cream has a surprisingly complicated microstructure. It contains ice crystals, liquid sugar solution, fat globules and air bubbles (the proportions of these change with the type and quality of the ice cream). At temperatures from zero down to typical domestic freezer temperatures it is not frozen solid because the sugar depresses the freezing point of water and the concentrated sugar solution remains liquid.
The amount of the liquid phase present decreases with decreasing temperature. If you imagine starting at zero C then as you lower the temperature crystals of ice form, which pulls water out of the fluid phase and increases the sugar concentration in the fluid phase. This depresses the freezing point until it matches the freezer temperature at which point the system is in equilibrium. Lower the temperature further and this forms more ice crystals, increases the sugar concentration still further and depresses the freezing point of the liquid phase still further. And so on. The liquid phase doesn't disappear completely until you get down to very, very low temperatures at which point the remaining sugar solution freezes as a glass.
It's this change in the amount of the liquid phase present that is causing the changes you have observed. As you warm the initially very cold ice cream you melt some of the ice crystals and get more fluid phase, plus the viscosity of the fluid phase decreases as it gets more dilute. Both of these soften the ice cream.
I should emphasise that this is a very simplified account of a very complicated rheological behaviour, but it should give you a basic idea of what is going on. The details are endlessly fascinating if you're a colloid scientist (or just like ice cream). For example sugar poisons the surface of the ice crystals and changes their morphology. In ice cream the crystals tend to be rounded blobs rather than the jagged crystals ice usually forms. This also affects the rheology since the rounded crystals flow over each other more easily.
Best Answer
If I'm not mistaken, a similar effect happens near all sufficiently cold bodies: moisture from the air condenses and becomes visible when cooled from room temperature, a process similar to cloud formation. The reason it stops forming after some time, near ice cream or otherwise, is because the object gradually warms up to room temperature. If the foggy layer is still enough (e.g. we have liquid nitrogen in a thermally isolated jar and between the nitrogen and air there is a layer of condensed moisture), it actually serves as an insulator and somewhat prevents the sublimation/vapourising of the cold object.
In labs which use liquid nitrogen or helium for cooling, an even more awesome thing happens, which is somewhat of a level up to the ice cream fog: the moisture not only condenses, but solidifies and forms ice on the metallic sections of tubes and containers.