El problema no tiene nada que ver con el script. Tú propio lo has dicho. Funciona bien en otras páginas. Probablemente el servidor SMTP que te han asignado tiene un alto tráfico o tiene problemas. Prueba con un script que sólo tenga un código mail() sencillo para ver el tiempo de respuesta. Con los resultados de esa prueba, vuelves a contactarte con tu proveedor.
