I dont know how big your veg plots are, but I (or more properly, my long suffering partner) has made some triangular cages to sit over the veg beds. Whilst the plants are young they stop the cats getting on them. Once the plants get a bit bigger, they can be removed cos the beds are too full for kitty to use as a loo.
although to be fair, I have only put these frames over 3 beds. I have sacrificed 1 of them as a cat toilet for my own moggies.