It seems to me that the original takedown notice was legally justified. It doesn't matter that it was a little harsh; that isn't enough to make it DMCA abuse.
The only thing that went wrong here was the hosting company's harsh response, by going far beyond what the DMCA required of them. The DMCA didn't cause the problem; the problem was caused by the hosting company's decision to shut down the site when it was not required by law and not demanded in the takedown request. And that's simple to resolve: switch hosting provider to a more reasonable one.