Listas negras

Buenas.
En la empresa en la que trabajo tenemos un exchange para correo interno y
POP y SMTP para el externo a través de ONO, quienes nos gestionan el
dominio. Nuestra IP (fija) es de Telefónica.
Hace ya un tiempo que cada vez mas destinatarios de nuestros correos nos
devuelven los mensajes diciendo "Acceso denegado". Uno de ellos decía que
estábamos en una lista negra.

He pedido ayuda a Telefónica y estos no me hacen ningún caso (me han
propuesto cambiarme de ip pero estando una semana sin acceso a
Internet...menuda solución!). Sé que hace un tiempo algunos servidores de
listas negras bloquearon la subred rima-tde.net de Telefónica por la gran
cantidad de spam que circulaba por ella.

¿Como puedo encontrar en que listas está dada de alta mi ip?
¿Como puedo dar de baja la ip de estas listas?
¿Tiene Telefónica alguna obligación de ayudarme?

Gracias.