I've heard about projects where they store heat underground - not sure if they use a certain medium or groundwater or something, but they basically pump heat into the ground during summer (and cold out into the HVAC) and vice-versa in winter. I guess ground itself - whatever is down there - is good enough. See also the London underground for an undesired underground heat storage.

But yeah, back in the day they would get blocks of ice from nearby lakes and put them underground, it'd last all year.