La funzione mail() (ma anche phpmail e simili) restituisce true se l'invio va a buon fine, ma questo non vuol dire che la mail arrivi effettivamente a destinazione o che venga accettata dal server di destinazione, vuol solo dire che è partita, affidandoti al valore di ritorno della funzione mail() non hai alcuna sicurezza sull'effettiva ricezione.

Detto questo, se su alcune caselle le email arrivano, il problema al 99% è quello che ti ho segnalato, specie se tra l'altro ci ho azzeccato sugli ISP che ti danno problemi.