The problem with the hoster. Advise what to do ...

Hello, dear habrasoobschestvu! I would like to share with you my problem and find out your opinion on this matter.
This morning, we stopped working some sites of our company. I will not bring links, you will consider advertising :)
I can only say that these are unrelated projects - a language school site and one non-commercial project. Sites are hosted by one hosting provider, so they immediately suspected something was wrong ... First of all, they unsubscribed to the support and received an interesting answer:

Good day!
')
Your sites are blocked for spam.

[SpamCop V2]
This message is brief for your comfort. Please use links below for details.

Spamvertised web site: http: // **** /
www.spamcop.net/w3m?i=z3823292233z27963047cab0a9070f6ebac7b0628a38z
www . **** / is 91.207.44.7; Wed, Jan 28, 2009 2:28:00 PM GMT

Spamvertised web site: www . **** /
www.spamcop.net/w3m?i=z3823292234z1b4ce3daad476f7216f6417eca2134b0z
www . **** / is 91.207.44.3; Wed, Jan 28, 2009 2:28:00 PM GMT

[Offending message]
Return-Path:
X-Original-To: x
Delivered-To: x
Received: from mail.act.dp.ua (unknown [127.0.0.1])
by sagator.gate.act.dp.ua (Postfix) with ESMTP id D9E4BB3A5DF;
Wed, Jan 28, 2009 2:26:07 pm +0000 (UTC)
X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on gate.act.dp.ua
X-Spam-Level: *
X-Spam-Hammy: 0.000-1--35h-0s - 0d - H * c: boundary,
0.001-1--24h-0s - 0d - HX-Spam-Relays-External: sk: ey-out-,
0.001-1--24h-0s - 0d - H * RU: sk: ey-out-, 0.001-1--17h-0s - 5d - Topic,
0.002-1--10h-0s - 6d - program, 0.002-1--10h-0s - 0d - 15.00,
0.002-1--8h-0s - 6d - sk: wwwope, 0.002-1--8h-0s - 6d - sk: www.ope,
0.004-1--4h-0s - 6d - 1963
X-Spam-Status: No, score = 1.7 required = 5.0 tests = BAYES_40, HTML_MESSAGE,
MIME_QP_LONG_LINE autolearn = no version = 3.2.5
X-Spam-Spammy: 0.998-13--0h-8s - 3d - Dinner, 0.998-13--0h-8s - 3d - dinner,
0.995-5--0h-3s - 2d - kids, 0.993-4--0h-2s - 6d - drama,
0.987-2--0h-1s - 6d - Students, 0.987-2--0h-1s - 6d - Teacher,
0.987-2--0h-1s - 6d - CLUB, 0.987-2--0h-1s - 0d - social,
0.979-23--3h-17s - 1d - philadelphia
X-Spam-Report:
* -0.2 BAYES_40 BODY: Bayesian probability is 20 to 40%
* [score: 0.3484]
* 0.5 HTML_MESSAGE BODY: HTML included in message
* 1.4 MIME_QP_LONG_LINE RAW: Quoted-printable line longer than 76 chars
X-Sagator-Scanner: 1.0.0-1 at gate.act.dp.ua;
log (status (report (drop (quarantine (clamd ())))),
status (deliver (modify_subject (SpamAssassinD ()))))
X-Sagator-ID: 20090128-162607-0001-05305-99wpWu@gate.act.dp.ua
Received: from ey-out-2122.google.com (ey-out-2122.google.com [74.125.78.27])
by mail.act.dp.ua (Postfix) with ESMTP id 7933BB3A5DE;
Wed, Jan 28, 2009 4:26:06 pm +0200 (EET)
Received: by ey-out-2122.google.com with SMTP id 22so21228eye.13
for; Wed, Jan 28 2009 06:26:05 -0800 (PST)
DKIM-Signature: v = 1; a = rsa-sha256; c = relaxed / relaxed;
d = gmail.com; s = gamma;
h = domainkey-signature: mime-version: received: date: message-id: subject
: from: to: content-type;
bh = DzsvXHDksssRGNyYtbMqeHJVguLJFOJYHf688RY0JB0 =;
b = qFFJcyWO + EX1AE8ixp0Uv + QI1ddMrg7pMb1meRQVFZM2hlySXk4RbXhAQMZRsQMLXS
O1wHPMynO52cjuxPCIIaJspxx7js3RZ5wJCimx5uyzq5vifLLGfybwxqzKUd9fUswqHO
WM9dWgHdnRKfCeYNH6YfPbv44igVxjiBNEcC0 =
DomainKey-Signature: a = rsa-sha1; c = nofws;
d = gmail.com; s = gamma;
h = mime-version: date: message-id: subject: from: to: content-type;
b = qYmKgdp7W8SmMIa3o45DiVfw4V00LbArZ7YBRA5o / aTIxUO4i4qlM0B / CGAZxUyZGd
rXgarWanA0rh1Cw86Q3VAik2tn1ZzV + l8thqs4wT0T9tcjv6GYvP8ypuHMoKY3cYzLtW
GsTa2WlO8cb9Dm9Q + DyjMY06Dt

And then they sent a letter that was “spam”:

Subject: Saturday Clubs (01/31/09)
From: International House DNK
To: x

Dear Students,

Welcome to International House DNK.

We would be delighted to see you at our Saturday clubs. It's a great
it is an opportunity to
t
also to improve your English.

There is a Guest entrance
fee of UAH 25 per 1 visit.

You can find the 31st of January program below.

Looking forward to seeing you with us.

Best wishes

International House DNK

* KID'S CLUB * Topic: Fairy Tales

15.00 = E2 = 80 = 93 16.00 Teacher: Vera

* ELEMENTARY PRONUNCIATION CLUB *

15.00 16.00 Topic: I'm Confused

Teacher: Natasha D.

* PRE-INTERMEDIATE VIDEO CLUB *

16:15 17.15 Topic: Thanksgiving Dinner

Teacher: Natasha D.

* HIGHER LEVEL SOCIAL CLUB *

16:15 17.15 Topic: Gays and Jobs

Teacher: Vera

* MOVIE CLUB *

17:15 Title: Philadelphia

Genre: Drama

Company name

tel. +38 ****
fax: +38 ****

skype ****
ICQ ****
info@****.com

www. ****. com
www. ****. com.ua

A member of the International House World Organization
International House 1953-2008
Celebrating 55 years of excellence

Dear Students,

Welcome to International House DNK.

We would be delighted to see you at our Saturday clubs. It's =
with your fellow-st =
udents but also to improve your English.

Clubs
Guest entrance fee of UAH 25 per 1 visit.

You can find the 31st of Janu =
ary below.

Looking forward to seeing you with us.

Best wishes

International House DNK

KID'S CLUB Topic: Fairy Tales

15.00 Teacher: Vera
ELEMENTARY PRONUNCIATION CLUB

15.00 Topic: I'm Confused
Techer: Natasha D.
PRE-INTERMEDIATE VIDEO CLUB
16:15 Topic: Thanksgiving Dinner

Teacher: Natasha D.
HIGHER LEVEL SOCIAL CLUB
16:15 Topic: Gays and Jobs

Teacher: Vera
MOVIE CLUB
17:15 Title: Philadelphia
Genre: Drama
- International House

We send such letters to our students. It contains various useful information for them - the time of extra classes, etc. Such mailing is made every Wednesday from September. The newsletter is conducted to those students who wrote in the questionnaires upon admission and agreed to the newsletter. When asked to stop sending it stops.

Next, the dialogue with the TP:

If I understood correctly from the address info@****.com I sent out SPAM
right?
What actions need to be taken to have the domain unlocked?

Good day!

Yeah, right. Also in the letter there is your contact information and your site.

We do not provide services to sites that send SPAM in general.

We are not engaged in SPAM, our weekly newsletter is held
customers every Wednesday. This is not more than 160 email addresses.
Mailing was made from the address ****@gmail.com
Perhaps our sites, and we have several of them, and all are hosted by you.
Have you been attacked? Tell me what action should be
to take

Good day!

We see that the mailing was intentionally made by you, or on your order.
The list clearly shows your data and the address of your site.
We refuse to provide services on a shared hosting.
You can get a backup copy and the balance if it is a paid hosting.

What should be done in this case?

PS Hoster - the company prohosting.com.ua