Exacto, si la IP del servidor está en las listas negras de SPAM, todo (o casi todo) lo que salga de ellas será marcado como tal.
Tu mismo puedes salir de dudas consultando tu IP en webs como:
http://www.dnsbl.info/ https://www.spamhaus.org/sbl/
(PD.: Existen más webs del estilo pero las que yo solía consultar eran estas dos)