Firstly, you have your conclusion backwards regarding how the energy changes when you increase the dielectric constant, AKA permittivity. For an ideal parallel-plate capacitor the capacitance is:
$$ C = \frac{\varepsilon A}{d} $$
If you insert a material between the plates with a higher permittivity (\$\varepsilon\$), then capacitance goes up. The energy stored in the capacitor (\$W\$) is:
$$ W = {Q^2 \over C} $$
If we are assuming charge (\$Q\$) is constant because the capacitor isn't connected to anything, then as capacitance goes up, stored energy does down.
$$ W = \frac{Q^2}{\frac{\varepsilon A}{d}} = \frac{Q^2d}{\varepsilon A} \\
\lim_{\varepsilon \to \infty} \frac{Q^2d}{\varepsilon A} = 0$$
So let's just reverse your question: what if the capacitor has some relatively high permittivity dielectric in it, then you remove it? Now the energy stored in the capacitor increases. Where's this extra energy come from?
The answer is simple: from the work you do removing the dielectric. If the dielectric is a sheet of something that you could pull out from between the capacitor plates, you would find that it's attracted to the plates, like a magnet. Of course it's not magnetic forces causing this attraction, but electric forces.
If you don't lose energy to anything like friction, all the work you did removing the dielectric from the capacitor remains available as the attraction of the dielectric back towards the space between the capacitor plates. That is, if you let it go, it will be sucked back into place, and everything will be as it was before you started. This attraction of the dielectric to the capacitor is a potential energy.
It might help to realize that as you remove the dielectric, the capacitance decreases, and the voltage must then increase. Since the charge is held constant, but this same charge now has a higher potential difference (voltage), there's more energy in the capacitor. The quantity of charge is the same, but by decreasing the permittivity you have separated the charge more. This takes work, like stretching a rubber band.
It might also help to think of this system in terms of something more familiar, like magnets. Say you have a horseshoe magnet, with an iron bar across the poles. When you pull the iron bar away, the energy stored in the magnet's field increases, and you put the energy there by pulling the bar.