Compressing air absolutely does store energy. It takes work to compress it, and work will be done when it is allowed to expand.
Yes, one way of measuring the stored energy is by the resulting increased temperature. Compressing air necessarily raises its temperature. And then if you want to you can transfer that heat elsewhere, go ahead. That's how air conditioners and refrigerators work, after all.
But in the basic case, it seems entirely accurate to say that compressing air does actually store energy. Just like raising a heavy object against gravity stores energy.