Just because a site can send emails through gmail does not discount the problem being with the server. It just means the site is skipping the server and going straight to gmail.

I have before used emails on a server (with Plesk rather than CPanel) and found it very hit and miss. But I would put my money on the problem being with the servers mail software. If you do get it working, chances are because its coming from an unknown server it will go into spam (might already be doing this if you haven't checked). This is why I would recommend to host your emails somewhere else like google apps (http://www.google.co.uk/intx/en/enterprise/apps/business/), lot less hassle for about 2$ a month!

Or use http://www.mailgun.com/ 10.000 free transactional emails every month + configuration is already set in Laravel

@cgoosey1: I can't just switch to Google apps since this is a customer application and it's unlikely that they are willing to migrate to google for one of their many apps..

I think Mailgun is probably the best option, I'll have to see if I get it working but that should not be too hard. Thx!

@elimentz Did you manage to solve the problem and send any email ?