In reply to Tony Naylor:
The area you are thinking of is known as San Bartolo.
I'm pretty sure that the rock is Siltstone, it is quite hard although it has the look of sandstone it is made with the finer particles of silt rather than sand. If anyone has seen the rock at San Bartolo you'll know that it has the appearance of mosaics in some areas, this is because it had cracks that filled with a softer material that wore away quicker.
You can use protection on it, but the places that I know of are somewhat limited. Having said that there are lots of places that it pops up across spain.
Anyway, I'm sure that it is the type of rock the OP was asking about.