Talk to them & see if they can implement SPF records. This might help you with the spamming some but I cannot see how any hosting company does not keep an eye on the emails that are being sent out.
Getting blacklisted is a horrible thing & can take weks to fix.
|