This may sound counterintuitive, but it may be because your script is too fast. In other words, you're overtaxing the number of thread processes the mail server can handle.
I had the same problem using ASP Cdonts object for mail.
This may seem abhorrent to a purist, but it worked for me: I put my mail script into a loop that cycled through 100 or 500 times for each mail message sent. I.e. all the messages got sent but on 1/100th or so of the time slice.
You may have to set timeout (which I dont' know how to do in PHP) on your script however.
HTH.
Sam Fullman
Compass Point Media