It could be a problem with the receiving side instead of the sending. You could try setting up a hotmail and/or gmail account (or even a variety of others) and change your script to send to each of those. If some of them get it (consistantly) and others don't, then you know that there must be some problem on the receiving end. This "problem" might still be in the way the messages are being sent, but that might be an issue with your server and is more complicated.
Here is an illustration of what is going on for me. I have an email script that successfully sends messages. These messages are received by about 2/3 of the email addresses I send them to. Those that succeed do so every time, and those that fail also fail every time. For the longest time, I thought it was a bad script, until one day I tried it on my friend's server. From there, every email was successfully sent and received every time (to the same email addresses as I used when the script was on my server). My problem has something to do with how the outgoing email is encoded or wrapped, but I can't be of much more help because this is where I get very confused. If you read about the mail function on php.net, the comments can help point you in the right direction for more information if you think your problem might be related to the one I have.