Order Emails not sent to customer

Hello.

Using 1.5.6, and in June, customers started to not receive their order emails. I called my hosting company, 3 times now, and it gets fixed to only stop working days or weeks later.

One time, the solution was to "reset stuff" (whatever that means)
The other time, I was taken down to php 5.4 from 5.6
The last time, it just started working again while on the phone.

The other day, it worked, and now it doesn't work.

I do:
Get customer order emails (the customer doesn't get their copy)
Get "contact us" emails
Get "new account created" notification

I am simply using mail, not SMTP settings.
I haven't made any changes to the cart nor installed any plugins

My hosting company is bluehost (been with them for 12 years)

Opencart error log shows no errors

Your service provider should provide you with the logs on the mail then.
Errors can occur when you are grey listed on email servers. If you have access to Cpanel then proceed to the logs.
In linux you can just cat /var/log/maillog or /var/log/httpd/error_log to see where there might be an issue.
Usually email failures occurs on the php or the sending server. Not OC modules.