It would appear that we have the honour of at least two of our IPs
being blacklisted by GMail. I've checked
http://whatismyipaddress.com/blacklist-check and we appear to be all
clear. Attempting to telnet in to their mail servers results in a
connection timeout.

Calling Google AU and being led down the whole "tech support" route
leads eventually to a recorded message informing me that they don't
offer phone technical support.

Anyone have any suggestions before I post a message on their forums?

Cheers,
Scott