Emails not being sent(or maybe recieved) even though tests are successful

I setup everything using smtp, test connection went fine. tried to send a preview, it said it was sent but I never received it.

So I setup using phpmail. Again send the preview, says sent, and I received it around 15min later. I tried sending again a few times, almost all of the time they never come. Twice they came but randomly late.

I use a hostgator dedicated server. Are there any host changes I can make to fix this?