The first step for a responsible pet owner when their pet exhibits a significant change (such as described here) is to take the animal to the vet to make sure that there are no health problems.
Health problems can cause litter box issues in several ways.
- A cat with urinary pain (an infection or stones anywhere in the system) will associate that pain with the litter box and will look for alternate sites.
- A cat who was declawed (either front only or front and rear), or a cat with arthritis, may find the litter uncomfortable to use, and look for softer places to go. A vet would be able to suggest which type of litter would be safe and comfortable for your cat to use.
- A cat with anxiety or other mental disorders may suddenly decide that they need different boxes for pee and poop, and if you're only providing a single box, pee does not need to be buried.
- Again, anxiety could cause feelings of insecurity, so they could be marking territory. This is especially true if the cat is not desexed (but I've had this problem even in a spayed female).
Once health problems have been ruled out, start looking for behavioral solutions. For one of our cats this phase took 2 years, so be patient and consider everything.
First, look at changes in the environment. Have you changed litter? Are the dogs new to the household? Have you moved? Etc.
If you aren't able to identify any changes (there's been a change, but sometimes it's hard to find), then start laying out litter boxes. One suggestion is to put a box everywhere he's gone. Another suggestion is to just put out a bunch and make sure that you clean the places he's been really well (use a blacklight to ensure it's gone).
Try different types of boxes (covered, uncovered, different sizes, different heights(sometimes an older cat will have a hard time getting into a tall box), different shapes, etc). Try different types of litter. Try different locations (some cats want a quiet place away from traffic, others want to be in the middle of everything).
Keep using the blacklight to track where he's going and make sure you clean where he's been really well. If you don't get rid of the smell, the cat will continue to associate that spot as a place to defecate. There are some cleaners you can use, like Nature's Miracle, or some common household products, such as vinegar. Don't use bleach to clean cat urine, as that can actually act as an attractant.
Some notes from my own experience:
We went through a phase with one of our cats where I changed litter suddenly and then he wouldn't go back to the box even after switching back to the original litter. I locked him in the bathroom with the litter box for about 2 days (with food and water placed on the other side of the room from the litter box), and then he was fine again.
We have another cat who has anxiety/territorial issues. We tried her on prozac, but that didn't help the litter box situation. Eventually, we set up her own litter box in the master bathroom, moved her food and water bowls to the bedroom, and made that her territory. When we are asleep or not home, she's in there with the door closed. She only interacts with the other cats when we are able to supervise. That's mostly fixed the problem (occassionally when we're home another cat uses her litter box, so we also switched to cat genies, a type of automated box, so she has a fresh box that's hers and we don't have to clean that box immediately if another cat uses it).
Good luck!