Solution for Bad IP

What to do when the server IP is on an email spam list?

[royalelephant]

It seems that one of my sites' demise in Google may have been due to some host server problems regarding spam/phishing that put my share-domain-ip on SPEW's list along with the spammers.

(In any event, I wrote to my host and didn't hear back from them, though the message was sent from my account control panel through their form to their addresses. I guess they just sux.)

In any case, I'm looking to bail out of my Host X, and have a few questions that I'd like to pose. Hopefully, a few answers will put me on the right course.

What's my optimum solution?
===========================

1) Should I transfer the domain to a new Host AAA, or is it unreasonable to expect that AAA will do a better security/anti-spam/phish/admin job than Host X?

1a) Can I tell in advance if AAA would do better than X?

2) Or, would it simply be a better solution to stay with Host X and pay more for a dedicated ip-addy?

2a) Or will this dedicated ip-addy also be open to abuse due to Host X's lax security/administration?

3) Or, is the opitmum solution to go to a new Host AAA?

3a) And get a dedicated IP?