This is quite an interesting question.
First - air is a (poor) conductor. See this earlier answer for some details on how well (or poorly) air conducts (especially when the relative humidity increases).
Next - vacuum as an insulator. You are right that once electrons are "in space", a vacuum doesn't provide much impediment. This is why cathode ray tubes (old TVs, oscilloscopes) and other vacuum tubes could work. But you might know that these typically contain a hot cathode: a filament that is heated, and that then gives off ("evaporates") electrons. The hotter the filament, the more electrons. This is a good way to regulate current in vacuum tubes (to this day, it's how X ray tubes work!).
The analogy of "boiling off" the electrons is quite good. Just as water, when heated, will evaporate more vigorously, so electrons will escape material more readily when they are hot. And just as some liquids have lower boiling points than others, different materials have different "work functions" - the amount of energy that an electron needs to be given before it can escape.
This was demonstrated, of course, in the early 1900's when it was shown that shining light of a certain wavelength or shorter could excite electrons and cause them to escape from metals (the photoelectric effect) but that longer wavelength light, regardless of intensity, could not. This was actually later understood to be caused by the particle nature of light and one of the first piece of experimental evidence of quantum mechanics (for which Einstein got a Nobel prize).
Back to the electrons and their work function. I wrote an answer about this a while ago: that was actually more detailed, looking at the velocity distribution of electrons that do escape. Taking a step back from that, electrons in a metal behave a bit like a gas: they move around randomly, bump into each other, and their velocities follow the Boltzmann distribution. This means there are always a few highly energetic ones around - more when the metal is hot. There is a natural energy barrier keeping the electrons bound to the metal, and electrons with energy greater than that can and will escape. This is described in this wiki article.
Perhaps you have already understood that a capacitor in vacuum can also lose charge when exposed to light: so if you want your vacuum capacitor to hold charge for a long time, you have to keep it cold and dark.