The tanks to hold liquid CO2 will likely be a lot cheaper than compressed air tanks because the required pressure is much lower. But they are going to loose a lot of energy to cooling the gas and reheating the liquid. I would be surprised if the round-trip efficiency is higher than 25%.
They claim 75% efficiency AC-AC [0], and they point out that there’s no degradation with time. What estimates are you using to arrive at the 25% figure?
Heat from compression is stored in a thermal energy storage system. Most likely something like a sand container.
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.