a parte le verifiche che hai già fatto (firewall e antivirus), il problema potrebbe essere proprio del server. Cito da Tiscali:
è molto probabile che l'inconveniente in questione dipenda da una delle seguenti cause: o una delle e-mail presenti nel server di posta ha una dimensione superiore a quella prevista dal contratto, oppure una di queste e-mail è stata spedita in un formato non riconosciuto dal Server di posta.
questo riguarda Tiscali, non so se si può estendere ad altri provider