I know nothing about caps that operate in a vacuum with nothing between them. I'd imagine that anything less than a perfect vacuum would still have air molecules between the plates. Just how much air - I couldn't know. Nor would I know how changes in the air volume would affect the cap.

There is little difference between the capacitance in a vacuum vs. capacitance in air.

The relative permittivity (a.k.a. dielectric constant) of air at standard temperature and pressure is approximately 1.0006, meaning that if I measured the capacitance between two conductors in a vacuum, then measured their capacitance in air, the capacitance would be seen to increase by roughly 0.06%.

 

Absolutely they can be. In fact, I've played with variable capacitors that were "Air Core" caps. Radio tuners. Tube type radios had these tuning caps long before PLL (Phase Lock Loop) tuners.

I know nothing about caps that operate in a vacuum with nothing between them. I'd imagine that anything less than a perfect vacuum would still have air molecules between the plates. Just how much air - I couldn't know. Nor would I know how changes in the air volume would affect the cap.

Exotic parts aside, the basic cap you find on all hobbyist work benches are not going to be vacuum sealed caps. But your point is valid.

http://maxwells-equations.com/materials/permittivity.php

If there is a non-vacuum dielectric between the plates the substance (that contains polar molecules) can be polarized (dipole moment) as it aligns or distorts to partly neutralize the electric field and the relative permittivity to vacuum (free space) increases as the capacitance of the capacitor increases because of the dielectric. The electrical energy is still stored as an electric field between charges. E=½CV2

A good question might be how does vacuum store energy?

It's electric charge that generates the electric field that transmits force and stores energy (The “field theory” view).
Pulling the charges apart requires work. The electric energy flows out from the path along which the charges move and appears as energy in the electric field.
The electric field does not appear instantaneously in space everywhere. This speed is the speed of light.