Sería recomendable también que pongas el código que usas .. que expliquese las condiciones de trabajo de PHP .. no sabemos si usas un servidor de correo Própio (un MTA o SMTP directo? .. o el servidor de correo de tu servicio de hosting....
PHP con su función mail() dependes del servidor SMTP (o MTA) que uses en la configuración de PHP ... Podrías hacer el envio de tu e-mail directo por SMTP usando classes como PHP Mailer (
http://phpmailer.sourceforge.net) .. así no depende de los servidores SMTP de tu servicio de hosting por ejemplo y usas los tuyos (que tal vez tengas más control sobre ellos o incluso estén más libres de carga ..). En fin . .son muchos factores a evaluar.
Un saludo,