Many times I had problems with emails sent from my applications were rejected by Gmail. One of customers told me that adding “Return-Path” header with the same address as “From” field should fix that and it worked like a charm! Quite interesting as I never found this documented.
Also, to avoid getting your emails filtered as “spam”, you can add SPF and DKIM records. The easiest way is to enable it directly on the mail server so you don’t have to change your PHP code at all. On cPanel it’s just a matter of setting two checks on Email Authentication page. I wish they were checked by default.