Pues primero, dejar de enviar spam o controlar que no se envíe spam desde tu servidor.
Segundo, comentarle a tu proveedor, pues casi por lo general es el dueño del espacio IP quien debe hacer los trámites.
Tercero, probar por ti mismo:
http://help.yahoo.com/l/us/yahoo/mai.../421-ts03.html