I've seen repeated mention of this in various sources, but no explicit quantification.
This means no working pure compressed air energy storage tech is in existence today -- a couple exist which add heat via combustion, one product used to exist which used an electric heater to keep a heat store warm. Both are thermodynamically non-ideal.
Based on pure theory, however, running two stages of compression to 200 bar (14.1:1 each), running perfectly adiabatically during compression and expansion, temperatures would reach to about 600 C during compression. If one didn't recover the heat of compression, and let the temperature of the compressed air drop to ambient, the temperature upon expansion would get to about -170 C. Pure thermal efficiency would be about 34%.
The results are so extreme / bad that one would choose a whole separate set of parameters and compromises. But that should show you the power of direct contact heat exchange.
I've seen some discussion of CAES using former natural gas wells for storage. I don't know the scale of operations there, but it could be large (meaning that relatively small amounts of energy would be stored or extracted at any given point in time.
Rock also serves as a pretty good insulator (R5 as I understand, and there's a lot of it), which might preserve some of the heat of compression.
In your example, is 200 bar a typical pressure for CAES? I see that as about 2900 psi for the imperial units types.
Salt caverns melt at high enough temps (above 200 C) and injecting hot air into a methane reservoir is not terribly advisable...
The constraints you raise on natural-formation CAES do raise some interesting challenges (or Hollywood movie plots).
My company, LightSail Energy, is developing precisely this technology.
www.lightsail.com
We're also developing the world's lowest cost pressure vessels to store the air.
I wish you had the money to invest in us too ;-)