Sobre las IP's clasificadas como SPAM .. podrías mirar por aquí (en general busca por "SBL":
http://www.spamhaus.org/sbl/ http://www.email-policy.com/Spam-black-lists.htm
Los temas legales de "antes" o despues ya tendrás que acordarlos a la hora de hacer tu contrato. SI no te fias de tu proveedor .. pidele que IP te van a asignar para tu mirarlo o en su defecto deja por escrito que si tu IP es dedicada para tí .. si aparece en ese tipo de listas se anula el contrato y que te devuelvan tu dinero. También puedes pedir un periodo de pruebas (aunque ahí no sé si te darían la IP que al final te quedes con ella .)
Un saludo,