I had that same problem, but on a somewhat smaller scale. Below are some ideas to speed up sending mail, some more effective than the other. Find out what the bottleneck is in your setup and choose the best.
1) Install a faster mailserver, like qmail or postfix. Sendmail is a magnitude slower in delivering and sending mail.
2) Don't use the PHP mail() but talk to the SMTP-server directly. I use the HTML Email Class from Heyes Computing (http://www.heyes-computing.net/) to do this. This package also enables you to send MIME-mail easily, examples are included.
3) Use several outgoing SMTP-servers. You can modify your script to do a round-robin on two or more servers. Using other servers makes it possible for the MTA's to keep up with PHP stuffing the mail queue.
4) Enlarge the PHP memory limit. Can speed up PHP.
5) Enough RAM. Make sure Linux doesn't have to swap to your HD when handling a lot of write actions to the mail queue.
6) Choose a fast filesystem on your queue disk, like ReiserFS, JFS or XFS (software), and/or use RAID striping on SCSI-disks (hardware).
7) Make sure your OS can generate a lot of parallel TCP-connections. The xBSD's tend to be faster than Linux.
8) Enlarge bandwidth to the outside. No matter how fast your server(s), if there's no way to send all that mail your stuck.
Hope this helps,
Jasper Veltman
Webminds IT