"Le mail rimangono in coda sul server e non partono neppure." è molto generico.
Va in timeout la connessione al server libero?
Viene droppata la connessione immediatamente?
Viene accettata la connessione poi chiusa?
Viene data una risposta SMTP durante la connessione che dice perchè viene chiusa?
Viene fatta parte della transazione ma alla fine rifiutata con un errore temporaneo?
Se dal server fai un "telnet mx.libero.it 25" che cosa ti viene fuori?