This year seems to have been particularly bad for paint vandalism to stones - so just a couple of pointers that may be of help if you come across stones which have been defaced in this way. Water-based paints can be as difficult to remove from stone as non-aqueous paints. If a stone has been defaced with what looks like a water-based paint don't assume that it's going to be easier to remove than a hard-wearing gloss paint.
Water-based paints are among the oldest known to man; the best known and simplest are those found in the c.14,000-17,000 year-old cave paintings at Altamira and Lascaux (although there is an example of a much older charcoal drawing on stone from the Apollo II cave in Namibia which is dated c.25,000 years old and a petroglyph from Olary Province in South Australia, the varnish on which yielded a date more than 42,000 years old!). Basically, to make one of these aqueous-based paints you take a pigment, say soot from your hearth or a coloured earth, mix it with a protein such as animal glue (to bind the particles of pigment together), add water to dilute it to the consistency that you like and presto! you have your paint. The ink used in the sophisticated paintings and calligraphy of the Far East is fundamentally just that - soot mixed with animal glue, scented with a little musk or incense and then hardened into sticks. When needed the ink-stick is ground on a hard stone together with a little water. The ink is then applied to paper or silk and when dry is, to all intents and puposes, irreversible. Very ancient and delicate paints such as those at Altamira and Lascaux of course are susceptile to modern-day hazards.
With paint graffiti, being able to reverse the damge is sometimes less of a problem with modern industrial paints than with some traditional ones. The problem with reversibility is not just the composition of the paint (water-based or otherwise) but also the nature of the support (the surface to which a paint is applied). It's easy to see that paint spilt on your polished coffee table is going to be easier to remove than the same paint spilt on your carpet - the former has a hard, compact surface while the latter has a soft, loose surface into which the paint is more easily absorbed. The same factors apply to paint on stone - the more porous the stone the more difficult to remove the paint.
You also have the problem of when to attempt removal - when the paint is still wet or when it's dry? paint on your coffee table is going to be more easily removed while it's still wet; chewing-gum in your carpet is more easily removed when it's hard and dry. Conservators therefore will try to ascertain the composition of the paint before trying to remove it. Unfortunately the problems don't end there; it might be resonable to use a fairly aggessive technique to remove paint on stone but not if there is delicate lichen or other factors to consider. The general rule when faced with any sot of graffiti (or any vandalism) is to to do nothing until a conservator has been consulted. Call the local museum right away or the conservation department at places like the British Museum, National Gallery or Victoria and Albert Museum (don't be put off my these grand-sounding places - they all have dedicated and enthusiastic conservators who will be there to offer immediate advice and maybe even practical support).
Finally, materials like charcoal and chalk (chalk of the blackboard variety) are strictly speaking pigments as they have little or no binder holding the particles together - that is why it's easy to wipe chalk of a blackboard and I would imagine also quite easy to brush or spray off stone). Once again, talk to a conservator before trying to do anything yourself.
Littlestone