Ciao,
o alzi il timeout (5000 non sono ancora tantissimi) o utilizzi uno script php-cli

http://freephp.html.it/articoli/view...olo.asp?id=106
http://it.php.net/features.commandline

da avviare via crontab

Quando gli utenti sono davvero molti puoi anche pensare di far dialogare direttamente PHP con il server SMTP.
Se vuoi provare quest'ultima soluzione nel week-end metto qui un link