As far as being themed or on-topic links, it takes more than the keyword in the anchor text to denote relevance.

Otherwise, you pretty much got it. As I said in my first reply, change the host, remove any links you having going out to those other sites hosted on that server and submit a re-inclusion request.

This is the only option. Any hosting company that recommends that does not deserve anyone's business as they are only looking for self- and cross-promotion.

__________________
Gennady Lager
SEO Specialist
SendTraffic.com