Part of that solution is to either sell a cleaning service that people only use occasionally, like deep cleaning of your floors, or to lock the client in to a contract that allows you to detect those private deals.

But the basic, "I'd like someone to clean my house once a week" doesn't work so well. People sometimes stop the cleaning after a bad experience. And sometimes hire the cleaner after a good one. And from the company's point of view, those look exactly the same. Customers will refuse 6 month contracts, and so there is no real recourse.