max_execution_time integer
Questo parametro imposta il tempo massimo in secondi concessi ad uno script per l'esecuzione prima di essere interrotto dal parser. Questo aiuta a prevenire che script scritti male blocchino il server. Per default è impostato a 30.
Il tempo massimo di esecuzione non è condizionato dalle chiamate di sistema, dalle operazioni sugli stream, eccetera. Vedere la funzione set_time_limit() per maggiori dettagli.
Non si può cambiare questo parametro con ini_set() quando il PHP gira in safe mode. L'unico modo è di disabilitare il safe mode oppure di cambiare il limite di tempo nel php.ini.
Anche il server web ha i propri timeout. Ad esempio Apache ha un proprio parametro Timeout, IIS ha una funzione di timeout sugli script CGI, entrambi con default 300 secondi. Vedere la documentazione del server web per maggiori dettagli.

In pratica il tuo script viene interrotto dal php prima che finisca di inviare tutte le mail (immagino che vengano inviate con un ciclo)

Se ti è consentito editare il php.ini (non tutti i provider lo permettono) cambia questa inpostazione con un numero più alto.

Una soluzione migliore è usare il crontab (ma anche qui dipende dal provider) e dividere l'invio di email in blocchi (es. 50-100) da inviare a distanza di alcuni minuti tra loro.
Non ti so spiegare di più proprio perchè il mio provider non lo permette

forse una soluzione potrebbe essere di inviare le mail in CC o CCN
Avevo già sentito parlare di questa soluzione ma non so se effettivamente cambia qualcosa.