para ver si es cosa de tu servidor, usa el WEBMAIL que te da tu Hosting, y enviate un Correo , y comprueba cuando se tarda en llegar, si ocurre ello tu hosting esta muy saturado, recomendarte ir a otro, si vees que es rapido, entonces el problema esta en tu forma de enviar el EMAIL, trata de que sea enviado desde un nombre de correo existente como
[email protected]
y que sea usando Sendmail o la funcion mail de PHP, para que el envio sea lo mas compacto y rapidamente posible, tu email debe ser tambien limpio para evitar que el destinatario su correo, este verificando posibilidad de virus de email de verificacion or que contiene Javascript ,Imagenes externas , etc etc