One way to do this is that the agency places a deposit in the contract, client places deposit+payment in the contract. Then when the job is done both parties confirm and the agency receives deposit+payment and the client receives their deposit. This way both parties are incentivized to find a mutually satisfying outcome.

It's not ideal in terms of funds used, but it improves the trust situation a little bit.