Gah. It seems that you can jump up and grab the top of the billboard, by holding down the R button, and then you can tag it while you hang there. Tch.
I now have enough points to move on to the next city, but I might just try and get a few more here before doing so – I only have one more fag machine to destroy (them evil smoking Germans, eh?) and I’ve just found the “tourist trail” goal, so might do that as well.