Cleaners that CCTV themselves.
It could be done with something as simple as a low-cost smartphone worn around the neck, or in the future something more sophisticated like Google Glass.
Lots of potential issues (would the cleaners accept this condition? would clients be happy to have a video of their house sat on a server?) but it's a potential solution to the trust issues inherent in the business - two main ones being 'is my cleaner dipping into petty cash' and 'is my cleaner actually cleaning'.