What would seem to be a silly question actually does have some depth to it. I was trying to scoop out some of my favorite soft name-brand ice cream when I noticed it was frozen solid, rather than its usual creamy consistency. After leaving it out for 10 minutes, it was nice and creamy again.
Notably, that amount of time wasn't long enough for it to "melt", as it would still not flow were the container flipped upside down, just long enough to "soften". So why is it that ice cream becomes stiffer/harder when cooled and softer when allowed to warm slightly?
My Hypothesis:
I think the "hardness" of the ice cream is largely determined by the properties of the ice crystals within, which change somehow with temperature. Now while I don't know how they do change, I'm fairly certain of how they don't.
You could view the temperature of the ice cream as infinitely many concentric layers, from a layer of maximum temperature on the outside of the ice cream given the ice cream warms from the outside in, to the point of minimum temperature at roughly the center of the ice cream. Therefore, it's fair to assume that partial melting and therefore decrease in size of each ice crystal is unlikely, as that would require a very thick "band" of ice cream layers to be at a transition temperature between completely crystalline and completely molten, which would only be likely with very slow cooling.
Best Answer
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.