Email non inviate ad alcuni indirizzi

Buongiorno,
da 2/3 mesi circa mi viene segnalato che alcuni utenti di Trusis non ricevono mail. Non sarebbe un grosso disservizio se, fra queste, non ci fossero anche le mail di registrazione al sito.
I provider dei destinatari sono tra i più disparati (Gmail, libero, yahoo, hotmail,..) e si tratta, molto "spannometricamente" di un 10/%20% delle mail di registrazione; quindi non c'è da scherzarci troppo.

Ho pensato a una richiesta (sulla pagina di registrazione) che va in errore/timeout, dati i frequenti rallentamenti sul server. La richiesta invece è sempre eseguita correttamente..quindi non può essere questo.
Come contro-prova mi sono fatto una pagina di test per inviare mail "custom" ai destinatari specifici che non ricevevano mail, e pare che questi non ricevano nemmeno queste. Quindi immagino sia un problema di server in blacklist o simili...ma ammetto di non essere ferrato sull'argomento.

Sapete aiutarmi?

P.S: Gli utenti dicono di non vedere le mail nemmeno nelle cartelle di spam dei client di posta.

Dovresti indicare qualche indirizzo di esempio, magari censurandone anche una parte.