Icy moons: why hasn't the ice sublimated away? Let's take Europa for example:
The predominant model suggests that heat from tidal flexing causes the ocean to remain liquid and drives ice movement similar to plate tectonics.
The heat generated from the tidal flexing has to go somewhere. Is it all carried away by the water vapor plumes we recently detected? Is more water from the ice cover melting away? Is it just radiated away?
I would expect it to cause sublimation as well: There is hardly an atmosphere (molecular oxygen at 0.1 micro Pascals, or 10-12 times that of the Earth), and a tenuous ionosphere.
And that same article suggest that the surface ice is also broken down by radiation:

the oxygen [...] is formed through the process of radiolysis, where ultraviolet radiation from the Jovian magnetosphere collides with the icy surface, splitting water into oxygen and hydrogen. The same radiation also creates collisional ejections of these products from the surface, and the balance of these two processes forms an atmosphere.
The hydrogen, meanwhile, lack the mass needed to be retained as part of the atmosphere and most is lost to space. This escaped hydrogen, along with portions of atomic and molecular oxygen that are ejected, forms a gas torus in the vicinity of Europa's orbit around Jupiter.

Or do we have reason to believe that any losses are compensated by ice being deposited from external sources?
I'll pick up on your example as it can be used very well for illustrating the main points:


First: The solar intensity in Jupiters orbit is less than 4 percent compared to Earths. So much less energy comes from the Sun which limits possible sublimation significantly
Second: Sure tidal flexing leads to fountains. These fountains blow material into space. But this does not mean that all the material will leave Europas surface forever. It can fall back or it stays in Europas orbit and returns to the surface due to the effects of Jupiters magnetic field or gravitational forces of the other moons.
Third: Sure the heat of the tidal flexing has to go somewhere. And it is largely irratiated away. As Europas surface is quite bright it reflects most sunlight away instead of absorbing it. This makes Europas surface quite cool (50-125K). Compare it with the darker neighboring moon Ganymede (70-152K). As you can see the albedo (which means the reflectivity of the surface) is far more important than the tidal heating. 
Fourth: Jep some of the water is split up by the radiation. This leads to an oxygen 'atmosphere' on Europa with 0.1 µPa surface pressure. While this is detectable it still is practically a vacuum. There is very little oxygen there, probably not more than a few hundred or thousand tons on the whole moon. Not enough to threaten the existence of moon with a mass of 4.8 * 10^22 kg


In summary: Yes, icy moons lose some of their material. But for exactly this reason they only appear in the outer solar system where the solar radiation is low enough to make this effect negligble.