Is one of these cats a lot newer in the household? When I got my third cat there was a pissing war over territory, literally. And my cats go outside freely! But darn it, the alphas had to piss in corners and on top of stuff because they needed to make cat number 3 understand that this place was theirs. This eventually stopped.