"Failing to pay the fee doesn't automatically break that contract."

IANAL, but aren't contracts only valid if there is consideration for both parties? If they're still letting him use their cars then the contract is probably legally binding, but if they've already cut him off then he can probably argue that the contract is invalid and he doesn't have to pay off the debt.