mail() returning TRUE does not neccessarily mean that your email was sent, it only means that the MTA ( SMTP server / postfix / sendmail / etc. ) accepted your email and will try to deliver it.
Meanwhile, the mail server might have 3,000 messages in its queue that need to get mailed BEFORE your email gets mailed or it might delay your messages for spam checking / another domain name might delay your messages for spam checking, greylisting, domain names which dont' respond in time, etc.
It's not the hosting providers fault neccessarily, and something like this should be expected when using the mail() function. True only means it was accepted and the mail server will try to send it, it doesn't guarentee it was sent, it was recieved, or anything at all other than that it was accepted by the MTA.
