Como ya te dijeron, puede ser por el sistema de correo de tu hosting. Y si usas byethost o alguno de sus resellers, los mensajes te llegan casi 24 horas despues.
Pueder usar el SMTP de Google, yo lo usaba en un comienzo y siempre llegaban los mensajes.