The issue these and similar businesses will face, I expect, is that once the cleaners become established with a household, there is always a large temptation to "go direct" and cut the agency out of the loop. THis is a win/win for the cleaner and the household. Typically the agency markup is split 50/50, and the cleaner makes slightly more and the family pays sligtly less.
There also isn't an easy way for the agencies to enforce non-competes or anything either, I'd expect.