Obviously their mileage differs, but I just couldn’t do it myself. Even if I’d had the dog for years, even if he killed the last cat so no more living there, I would never again be able to look at him and think, “Good boy.” He’d go to the shelter immediately. If he were too old/established with me to be a good adoption prospect to adjust to a new catless home (hypothetical extreme: 20yo dog, and this had been his lifelong home), I’d have him PTS, not as “revenge,” but because rehoming would be cruel to him. But I just couldn’t continue to live with a cat-killing dog, even if no more feline victims were available at my house.
OP, glad the dog got returned, and I hope the rescue is honest in forwarding the information to others.