Hola donfalcone,
Sin tocar nada, podrias probar con
set_time_limit cambiar el tiempo maximo de ejecución de PHP.
Si eso no funciona o no te sirve podrias separar el envio de 400 en varios de 100 (por ejemplo). Sería como "paginar" la consulta de a 100 resultados, enviar esos 100, esperar unos segundos y seguir con los siguientes. Maneras de hacer esto hay varias pero esa es la idea básicamente.
Saludos