> But why was I paying them for backups that they wiped along with my server?
Sounds like you weren't paying for backups.
tl;dr - customer stops paying service provider, and service provider stops providing services. Customer is upset.
This one's on you.