Hia,
I recently had a similar problem and it turned out my mail was being blocked by spam filters at various recipients and it just seemed to take a while to get through to others (a few hours in some cases!)
If you are on a
VPS Hosting or Dedicated you can nip into WHM and check the mail queue, see if your mail is sitting there, or run the Mail troubleshooter.
Otherwise I'm afraid this one is down to the support team, not much more I can suggest I'm afraid apart from list a few issues that has stopped mail() reaching it's final destination for me in the past;
- No reverse DNS on my server's IP,
- No SPF record on my domain's DNS zone,
- Oh, and of course, incorrect email address syntax
