The annoying thing is that this is obviously a setting within Gmail, because our other server is sending the same volume of messages without any issues. Right now it's getting slowly better so I'm not keen to set up extra servers for what I hope is a transient problem.

Other suggestions have been to send all Gmail messages via our working server, but that would cause a spike in it's traffic and I'm worried we'd get the exact same issue there.

Both Microsoft and Yahoo have responsive processes to solve this problem, it's frustrating that Google is so opaque.