Se ti dice che è stata spedita vuol dire che la funzione mail è andata a buon fine.
Da lì in poi non è più compito di PHP gestire l'email, ma del mailserver di partenza e di quello di destinazione.
Controlla che le email non vadano a finire tra lo spam.