Wow. I'm totally not shocked. A bargain bucket cheapo hosting company runs into a technical issue and massive outages and uncertainties on data integrity ensue.
That my friends is why you do sanity checks in your scripts. If your host has a wildly different amount of clients than say an average, then you just simply don't delete them. A good practice would be to also backup these deleted machines for a week via the cleanup scripts.