To be completely honest, if your cats and dog have sprayed/pee'd throughout your house to the extent you're describing, there is absolutely no way you're ever going to get your home cleaned up enough where the cats can no longer smell the urine.
Even if you can't smell it anymore, they still can. A cat's sense of smell is approximately 14 times better than ours.
Once the urine soaks into wood and baseboards and wicks up into the drywall, it's very difficult to remove the odor so it's undetectable by people. Your cats will still smell it.
The kindest thing you can do for yourself and the 2 stressed out male cats, is to re-home them to single cat households where there are few if any outdoor cats.
Some situations are just not workable. I believe yours has become one of those.
My daughter went through a situation similar to yours. It ended up that the one cat who was the "pee Leader" just wanted to be outside and once she started letting the cat out, the peeing stopped.