se è una casella gratuita (e spedisce da locale utilizzando il provider di connessione come server in uscita, tipo out.alice.it), la mail non viene "firmata" dal server di libero. quindi mancano informazioni nell'header della mail.
questo cosa, gmail ed altri, la vedono male e quindi la mettono nello spam.
per questo motivo sto pian piano eliminando i miei account su libero.
edit
si potrebbe ovviare passando dai server gmail settando un indirizzo aggiuntivo:
http://www.motoricerca.net/gmail-non...dirizzi-email/
non l'ho mai provato, ma vale la pena tentare.
ovvio che tu non puoi farci nulla, è il cliente che si deve interessare