Cheap teflon-like coatings for vehicles and buildings, that paint won't stick to.
Won't necessarily work, since I've seen graffiti on rocks by the highway in exurb areas. People will spraypaint anything they can. That goes double for gang-related graffiti, since those people are probably the most dedicated graffiti taggers out there. Not to mention that's going to be very expensive for any city or government to pay for. Probably cheaper just to pay more into the police force and get the cops to teach kids a lesson through community service and various other programs. But as noted earlier in this thread, in many cases the police don't have the time to deal with petty crimes in such a manner because they're dealing with serious crimes instead.