Hold them to the contract.
If you are a component to their project and their overall project is failing so they want to cut your component? If so they paid for your services and if they are failing their overall project that is not on you. Keep the money they paid you for your product that was outlined in your contract.
If they are a component or part of your project and want to quit because they underbid the portion they are responsible for and now want to bail before taking a loss that is also their fault and hold them to finishing their portion of the project for whatever amount you agreed to prior.
Not sure what else to say without knowing more and this is taken from construction experience with dealing with various sub contractors so it may not hold true as much for the tech sector.
Take all information as anecdotal evidence and I am not a lawyer.
"Refund Policy We don't offer refunds, but you may cancel at any time."
In my opinion you do not have any obligations to refund money to them for services they had already used.
Maybe if they somehow did a pre-pay for say a year's worth of operating costs up front based on an estimated usage and then bailed before they used it all maybe there may be some grey area where you owe them a prorated amount of what they didn't use.
Much like say you get a car insurance policy and pay for all 12 months up front, then all of a sudden you get a new car 9 month into it and get reimbursed for the 3 months you didn't use.
In my opinion any services they used they owe your company for.
Services they were planning to use but didn't actually use yet may be a grey area.
If you do not allow them to pre-pay for blocks of use ahead of time this isn't an issue.
Again I'm not a lawyer.
I would reply with something like:
"Unfortunately a refund would not be fair to our team based on the work we have done so far for you. However, you are an excellent client and we would love to give you some type of concession for future and we can offer you xyz. I hope this helps you. Let me know if you have any questions on this concession offer"
Use words where you make the client feel guilty about asking for refund (because frankly, they shouldn't). However, you still sound like you are trying to help them. Win-Win.
This helps keep both of you happy, they are seeing progress and you are seeing payment for work completed.
Client management is a difficult thing. I would assure them that the project will be completed, it is taking longer than expected because of x,y and z. That you will do a better job of keeping you informed of issues like these in the future. Give them an updated date that you can deliver early on. If you can break the remaining work into milestones where you can show them incremental progress.