Not receiving emails

I have just about finished setting up my wordpress website and just tested the contact form and cannot get any of the forms to send through to any email address. I am also not receiving admin emails e.g. when a new user is added etc.

I have very little experience with this sort of thing so I may be doing something incorrect that is very simple and I am just not aware of it.

I have also tried to setup at WP Mail SMTP plugin but this has not worked either.

I’ve tried calling the hosting company crazy domains and asked them about the issue and they just told me that its impossible to have send the email through to a google apps account.

I dont know for sure but it may be something to do with my settings in the hosting???

Details are:

WP version 4.0.1

my host/server settings etc are:

Crazy domains

Name Server 1: ns1.dnspackage.com
Name Server 2: ns2.dnspackage.com

A Records
deaux.com.au ? 27.124.116.225
https://www.deaux.com.au ? 27.124.116.225

CNAME Records
ezewuji4shru.deaux.com.au ? gv-5fyyt2o4gl2wnw.dv.googlehosted.com

MX Records
deaux.com.au ? ASPMX.L.GOOGLE.COM
deaux.com.au ? ALT1.ASPMX.L.GOOGLE.COM
deaux.com.au ? ALT2.ASPMX.L.GOOGLE.COM
deaux.com.au ? ALT3.ASPMX.L.GOOGLE.COM
deaux.com.au ? ALT4.ASPMX.L.GOOGLE.COM

Thanks in advance for any help.