For me, maybe an 18-24 hour fast, depending on how I feel the next day. I don't even really consider myself to have "non-paleo days", but rather non-paleo meals or social situations. I don't need a day to eat non-paleo food, because I love what I eat. That helps me to not obsess over food when going out with my non-primal wife or friends. I just eat reasonably, for the most part, but also enjoy whatever is available.
Most times, I just go back to my regularly scheduled routine. This isn't a diet, so there's nothing to fix. My body tells me when it's hungry, and after being primal for this long, the insulin-related "hunger" reactions feel different than actual hunger pangs.