Business emails all going to SPAM

Hey Experts,

A Real Estate Client of ours has found out that email they are sending both internally and to their clients (and potential clients) has been incorrectly recognised by Google as SPAM, so is arriving almost exclusively into recipients' SPAM folders.

An MXTOOLS check confirms that their domain has NOT been blacklisted.

I have run many tests from their emails and only have consistent success in sending to Gmail, Yahoo and an independent cloud-based exchange equivalent when I remove the sender's entire signature before sending. All email users at that company send emails with a signature that includes the usual office number, mobile (cell phone) number, email address and company specific picture. It looks to me as though Google have set it so that the SPAM score from this domain is so low as to block almost everything from them.

I'm a bit confused as to how to proceed, given that they have their own non-gmail domain from which they are sending, however they are using Google Business Apps.

For what it's worth, I wonder if their recent (Q3/ A4 last year) domain change has made a difference, as they have changed from an Australian .com.au domain to a more international .com one.

I'd love any wisdom you may have to share on this as the issue's heavily impacting their business.

Thanks guys...