Emails sent using PHP mail() function are not reaching recipients. Sender's domain is a domain that has a website hosted on the same Hostgator server (which I believe is a requirement).
After a bit of troubleshooting I found that the issue occurs if recipient's domain has a website hosted on the same Hostgator server as well (but email on a different system).
My theory is that when recipient's domain matches a domain hosted locally, the server tries to deliver the email locally rather than sending it out. Checking mail logs would allow to confirm that, but shared hosting Hostgator accounts don't have access to mail logs. I tried raising this with Hostgator support, but didn't have much luck - they kept insisting I need to speak to either GoDaddy or Gmail...
I didn't persist much further, instead setup a simple PHP PEAR script to send via an external SMTP server (AuthSMTP).
Hostgator shared hosting