Email confirmations sometimes not sent - host issue?

I am having an issue, i am 99% sure its HOSTING RELATED.
I have called and of course they insist its not on thier end, but that it must be my scripts.
The host is Blue Razor (which is really godaddy).
Im curious if anyone else is having an issue with this host and the emails being sent out upon email confirmation?

For some time now we have had delays with emails being sent out from orders.
the order confirmations can take up to 1-2 hours to receive at times.
And sometimes its seems like there is a slow response in just viewing pages.
Now we have an issue with the email confirmations not going out sometimes when an order is placed.

I suspect that the server is just really busy and overloaded. I have suspected this for a long time since we have emails delayed, but now that the emails are not going out sometimes, Im wondering if it is because they are TOO busy at the time the order is placed.

We have not made any changes to the email scripts in quite some time (at least 4-5 months) and the issue just now started on july 5. I have called tech support for the hosting company, and while they find it odd - they insist that noone else has reported this issue and it MUST be my scripts.

I have tested everything i can think of to test my scripts. Due to the issues and me not thinking its my scripts, my client is considering having me move the site to another host. But before i go through that PITA i want to make sure that it really isnt my script!

TESTS I HAVE RUN
(IF YOU CAN THINK OF ANYTHING ELSE TO TEST - PLEASE SEND ME YOUR IDEAS)

We have 2 instances where emails are sent
- email confirmations upon ordering
- an admin feature to resend email confirmation (same email except the stored data populates the email instead of the session data)

RANDOMLY when orders are placed an email will NOT get sent.
If we have 10 orders, 3 might not get sent.
If we try to resend the emails, it may get sent, it may not get sent.
But if we try enough times it eventually does get sent.

It has nothing to do with a particular order.
We have successfully re-sent order confirmations that did not initially go when the order was placed.

Additionally, orders that did have successful email confirmations go out, we have tried to resend and had them not go out.

This also proves it has nothing to do with a particular email address.

There are NO ERRORS when the emails do get sent.
So the email script is processed successfully wit no errors.

Additionally there are NO errors when the emails DO NOT get sent.
So the script is processing as far as i can tell - there is no error being generated that is bounced back to us. So there is no hint during the process of checkout that the email didnt go out - everything seems normal. Same when you try to resend emails on the backend - there is NO error or anything. You just have to simply wait an hour or so to see if it the email arrives.


I cant think of anything else to test.
And my tests and the issues seem to be HOSTING related to me.
Anyone have any ideas on more things to test, or do you have an opinion that maybe it really is the host?

Thanks
Sam