Depends on the amount of the claim. Engaging legal advise isn't cheap, $250-$600+ per hour. For a lawyer to read over contract and go through timeline of events, draft up response / claim and send out, I would be surprised if it was less than $1k, probably more like $2 - 2.5k, then there is the response from the providers legal team with suitable read through and consideration by your lawyer, another hour or 2 billable time, it all costs and it all adds up very quickly.
Best case scenario, Provider A agrees to refund amount claimed. Weigh up the cost of legal fees against the best case scenario and add in time and effort in battling provider A, is it really worth it?
Only bizarre thing in this is that they not only took all money due as if services had been provided AND an early termination fee. If they have received all monies due under a contract, how can they then charge a fee on top for breaking the contract? Pretty sure thats against the contracts act as there was no financial loss to provider A through the breach (ignoring the dates). I would think that if Provider A began taking payments in July, they would be hard pressed to argue that the contract hadn't commenced then (they had received consideration for services).