If you agree to pay $200 for cleaning, and they charge you $200 and don't clean, then you have a services-not-rendered chargeback. If they charge $10,000, then you have an unauthorized-amount chargeback. As you are experiencing right now, a services-not-rendered chargeback can be more difficult to pursue than an unauthorized-amount one. For the former, you have to show the services were not rendered, while for the latter you only have to show that you didn't authorize the transaction. Moreover, the latter is more likely to be treated as a criminal matter, while the former may be brushed off as a civil one (it's not like people generally get arrested for not showing up to work, even if they've been paid in advance).
You should push back on your bank, though. Services-not-rendered is a perfectly valid chargeback reason, and the person who said you can't charge back is at best misinformed. Perhaps they thought is was a wire transfer or something. Insist on filing a chargeback. It would be easier if it were a credit card, so that's something to keep in mind in the future.
Cite for services-not-rendered chargebacks on debit cards:
Can I Dispute a Debit Card Charge That I Willingly Paid For?
Yes, you can dispute a charge for all transactions you made willingly if the service was not rendered or the product was not as described. Just be careful to meet all the merchants’ requirements from the terms and conditions of use, and you’ll win this fight easily.