It would appear that we have the honour of at least two of our IPs
being blacklisted by GMail. I've checked 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?