About the "oldest vandalization" - I remember seeing an exhibition on Pompeii and Mount Vesuvius (79AD), and there was a bunch of examples of preserved graffiti. There seemed to be lots of "Mr Speaker was 'ere", even then!
[edit 2: http://www.pompeiana.org/Resources/Ancient/Graffiti%20from%2... - lots of examples of texts they found: "Daphnus was here with his Felicla", "Restitutus has deceived many girls", "O walls, you have held up so much tedious graffiti that I am amazed that you have not already collapsed in ruin"!]
"If anyone does not believe in Venus, they should gaze at my girl friend" Reading these just emphasizes to me that these are people just like us. We might wear different clothes and speak different languages, but we really are just the same as people were thousands of years ago.
"If anyone sits here, let him read this first of all: if anyone wants a screw, he should look for Attice; she costs 4 sestertii." Seriously, I'm pretty sure I saw this same graffiti in a truck stop restroom stall once.
I can better that by a few thousand years. Egyption pyramids have graffiti tucked into corners, graffiti left by builders. I doubt there is any structure that doesnt have some improper mark left by someone during construction.
A nice example of this can be seen in the British Museum where one of the Assyrian Statues has a board game scratched into it's base, presumably by bored guards. There's a picture of it in this article http://www.bbc.co.uk/news/magazine-35669056
"If anyone sits here, let him read this first of all: if anyone wants a screw, he should look for Attice; she costs 4 sestertii." Seriously, I'm pretty sure I saw this same graffiti in a truck stop restroom stall once.