I am not a lawyer, so take this as my own personal opinion:
It sounds like a common situation these days, abuse of ip law to stifle criticism. From what you've described, there is no trademark infringement whatsoever, you are perfectly within your rights to mention a company name and to also offer critiques of their service. The comments may be defamatory or libellous, so they may have a case there, it depends on the actual content. But as these are user submitted reviews, Section 230 safe harbors should apply, assuming you are in the US.
You mention the need for a copyright lawyer, but this is not an alleged copyright issue. As such, the DMCA is also irrelevant. If it were copyright, you could file a DMCA counter notice. But with it being trademark infringement, there is no counter notice, and no DMCA protection for your host, which is why in 99.9% of these cases, web hosts take the easy route and disable the content from fear of legal action. It would be nice to say 'find a stronger-willed host who understands ip law', but good luck finding one.
From chilling effects:
Trademark owners do not acquire the exclusive ownership of words. They only obtain the right to use the mark in commerce and to prevent competitors in the same line of goods or services from using a confusingly similar mark.
As you can see from the above, scathing reviews of a company should not considered trademark infringement, as there is no 'competitor', nor any attempt to cause confusion. It seems abuse of the law and that letter was written knowing full well that your host will take down the content to avoid any hassle. If you are somehow affiliated to one of their competitors, this may lead to other problems, although I still don't see how this could be seen as trademark infringement.
There are of course other things you can, going public is one of them - blogs like techdirt.com love to write about these cases. You could hire a lawyer, or maybe try public citizen or the eff. Paul Alan Levy of public citizen seems to know his stuff and writes a very decent retort to ip bullies.