I had the same problem always any time I used a mail account inn CPanel.
I just solved it today, here is what I did.
Anyway, I made a new mail acount in my CPanel, with 250mb quota, tried to send emails to ma gmail,it worked,responded back and it didnt work.
Another susspicius thing was, that i thought I was sending an email from my newly created email account but on Gmail I would get it from a different email from the same domain (it was my CPanel username email, which doesnt seem to have any quota assigned to it or any space on the server). So I had a chat with the support service, but they tld me to login to the members area and file a ticket.
So I logged in to the members area,but first clicked a "Webmail" button there, which basically sent me to CPanel but didn't have the login screen for the whole CPanel interface but just asked me to login to my newly created email account directly, so I did, and voila! All of my test email messages from gmail were there received in the inbox! :)
DNS MX record