Meiner Erfahrung nach haben Unsauberkeitsprobleme ihre Ursache häufig darin, dass Katz etwas sehr unangenehmes mit dem Klo verbindet. Das könnten in Eurem Fall ja auch Schmerzen beim Pinkeln (unerkannte Blasenentzündung) oder Mobbing durch die Erstkatze sein. Und da reicht es völlig, dass Katz es irgendwann mal negativ verknüpft hat, um dann das unerwünschte Verhalten über Jahre zu zeigen
Erster Schritt wäre also, rauszufinden, woran es liegt, was nach so langer Zeit schwierig ist. Ansonsten bleibt fast nur try-and-error übrig. Also: Katzentoiletten komplett umgestalten (neue Toiletten, andere Streu, anderer Platz). Kater von Katze und Hund räumlich trennen (um rauszufinden, ob Stress/Mobbing die Ursache ist). Wenn Du sie nicht rauslassen kannst, besteht die Möglichkeit, einen Freisitz zu bauen?
Viel Erfolg!