The energy used to liquefy the CO2 is the bulk of the energy stored. They don't throw it away afterwards. The the liquid-gas transition is why this works so much better than compressed air.
of course they are not throwing the energy away. but by using a working fluid that changes phase they are trading away energy efficiency for power density, for the same reason that steam engines are less efficient than stirling engines.
