Mail Function

Hi, I have a web site that is going to have around total of 10-20 thousand unique users, about 1000 unique hits per day on shared hosting. I have been using PHP's internal mail mechanism with the local smtp server on my hosting company, but it is more like a hit-and-miss kind of thing. And, there are users complaining that they are not getting any e-mail. Can you guys please provide advise as to what the problem might be? I don't think it is the local SMTP, because the way SMTP is configured is pretty solid, and once you submit internally (not via port 25), it should retry till it delivers it. So, I am thinking it might be because of headers or something else. So, should I use a more sophisticated mail library? Can you recommend any? Thanks...