1) Verifica che il tuo server SMTP NON accetti il Relay e che sia in grado di autenticare gli utenti (se non è in grado di farlo cambia software)
2) Collegati qui
http://openrbl.org/
e verifica in quali liste è presente il tuo IP
3) Dopo aver configurato il tuo server SMTP come da pto 1), fai ricontrollare a tutte le liste di cui al pto. 2) il tuo IP: nel caso in cui la configurazione sia OK, al massimo in un giorno dovresti uscire da tutte le blacklist.