Traffic from the GWIA was seen to try the secondary MX record for an Internet domain, before either failing or retrying on the primary record. The destination Internet domain uses Message Labs as their mail relay/Anti Spam/Anti Virus solution and when the GWIA first tried to connect, it connected to the secondary MX record.
Message Labs have a very aggressive change policy so that the value of their MX records changes on an almost daily basis, thus helping to both mask and create the underlying issue. The GWIA was using a Windows 2000 server as the DNS source and the caching/refresh levels set upon the DNS service by default, combined with the Message Labs regular value changes resulted in the GWIA being misinformed as to which MX record to connect with. Changing the DNS server to SLES10 BIND resolved the issue.