Si vas a usar Sleep (de la primera opción) yo usaría AJAX porque si la máquina se duerme 3 segundos, son 3 segundos más que el usuario tiene que esperar. Al usuario le gusta más la pantalla con la cosita dando vueltas de cargando que pongas con el AJAX que la pantalla quieta. Si el usuario tiene una conexión rápida se dará cuenta.
Otra cosa que tienes que hacer es comprobar el retorno del valor de mail. Mail devuelve true si lo envía correctamente (sin contar con que te hayas inventado el mail), o false si hay fallos. Guarda un registro de cuando hay fallos y verás con exactitud el nivel del error. Me imagino que hay una forma de extraer exactamente el fallo, pero ahora no se me ocurre ninguna. Tampoco es k lo haya pensado mucho XD. Esto último es lo que ha dicho el que tengo encima.
De todas maneras lo primero que dice PHP.net es que mail no es una función muy efectiva para mandar mail ya que abre y cierra el servicio para enviarlo.
En "From: destinatario yo" pondría un correo ficticio, tal y como
[email protected] o algo así. Quizás el parser de tu servidor lo bloquea por que lo considera de spam.