>...there are a lot of wild plants that would probably give up their dye without the use of inorganic mordants...<

True, but they are very fugitive. We've all had the experience of kneeling or sitting on the grass only to find a nice green patch on our clothes afterwards - the colour (dye) generally fades, changes colour or is washed out fairly quickly though. A dye only becomes more stable when it's mixed with a mordant and becomes a 'lake' - even then it's susceptible to fairly rapid fading at even moderate levels of natural or artificial lighting. I know of one exception to that however and there might be others. The exception is alder, which gives a lovely golden brown without the need for a mordant, and is pretty stable for at least a year out of doors.

Japanese prints are a prime example of the use (and hazards) of vegetable dyes; one might ask why vegetable dyes were used for these prints at all. The answer is simply because if ground down mineral pigments such as malachite and azurite (both used extensively in Far Eastern paintings) had been applied to the finely cut wood blocks the blocks would have worn down very quickly indeed. Japanese prints were also considered little more than the posters of their day and it didn't matter much to the people who bought them if they faded pretty quickly.

Bringing the discussion back to paint on stones and other external structures, perhaps you could apply a dye to a white surface such as gypsum; it wouldn't have lasted very long but might have been quite impressive while it did. I can't see that being done on large structures such as Thornborough but perhaps on stones, totem poles, and figures of gods or animals might have been painted in this way.

Do you know very much about traditional British dyes, moss, as I'd like to learn more. One other snippet of info that might be of interest is that some plants that were use as dyes were also used as medicines.

Fascinating stuff, and worthy of further study in the context of ancient colouring agents.