Daffe har nevnt spf, da spør jeg, har du noen epostadresse som du kan få bounce meldingen tilbake på?

Og en annen ting som kanskje ikke er satt opp riktig:
Gmail er ikke særlig tilhenger av smtp servere som ikke krever autentisering, sjekk at du ikke er open relay.