pamimo, quizás algún otro usuario del servidor compartido que usas si hizo spam, y metieron la IP del servidor a alguna blacklist, afectando a todos los usuarios.
Esto puedes verlo en
http://www.dnsstuff.com/
En mi caso, tengo un servidor dedicado. Sólo yo uso los recursos de éste, no realizo envío de newsletters siquiera (como para sospechar que hago spam) y no estoy en ninguna blacklist. Es rarísimo.