I think it's important to note that just because the mail() function returns success doesn't mean your mail was delivered successfully. It is your mail server which ultimately delivers the message to the recipient.
So if mail() returns true but you're not seeing your emails go through, check your email logs to ensure the messages are being delivered as you'd expect.
I'm actually working on an SMTP mailer Extension for PHP in my spare time so that I can use the reply codes from the recipient's mail server to confirm receipt of said messages.
PHPMailer does support delivering mail directly to the recipients mail server via PHP sockets and SMTP, but I'm hoping for some speed increases by writing the same functionality in C.