Non ho capito se in black list viene messo l'smtp di telecom o il vostro ip pubblico.

se il tuo caso è il primo dubito che telecom riservi un server smtp unicamente per voi... la sorgente dello spam che ha portato l'ip in BL potrebbe quindi essere qualsiasi cliente telecom con diritto di uso di quel server. In questo caso la cosa è unicamente di pertinenza Telecom. Contattali.

Se invece in BL finisce il vostro IP bisogna verificare se è stato bloccato solo il vostro ip o tutto il netblock di appartenenza (in quest'ultimo caso, ancora una volta, potrebbe non essere un problema direttamente vostro ma di telecom). Hai provato a vedere quale delle liste antispam vi blocca? Se ti serve una mano puoi darmi l'IP in un messaggio privato.
Per quanto riguarda la tua configurazione... la casella catch all non influisce nel problema, al massimo potrebbe portare spam nelle vostre caselle.
La cosa da verificare invece è che non esca spam dall'azienda, volontario o involontario. Esitono dei malware che installati sui pc li trasformano in perfette macchine spara spam.
Dalla lan è possibile usare direttamente server smtp esterni invece di passare da quello interno?
Il server interno ha rilevato attività sospette?
Come prima cosa comunque analizzerei le BL.