Here in the pacific northwest we have a wild annual geranium that cats hate. The roots smell just awful though the plant itself has no real smell. I let them grow where ever they pop up. Maybe look around to where they are not pooping and see if there's a common denominator. That might give you a hint. You can still lay down the chicken wire in your vegetable area if you're worried about contamination. Someone else mentioned the motion detection sprinklers... those work great too though they cost. It's possible there isn't a single solution for your entire yard, you may have to find different solutions for different parts of your yard. I dunno.
