mande le email sempre dallo stesso server? il problema potrebbe essere che l'ip del server da cui partono le email è in una o più blacklist.
se ad esempio se su un server dove ci sono piu siti e il proprietario di uno di questi siti manda x email di spam e mettono in blacklist quell'ip anche le tue email non vengono ricevute da alcuni provider. hai per caso notato se il provider degli utenti che non ricevono le mail inizia per la lettera l.... ?