We've finally found the issue.
Akaimai was sending it's own user agent, Akamai-Edge
, through to our servers in the request for the page.
In doing so, our servers were returning different markup based on the user agent. (Our site runs off the CMS Sitecore, which has user-agent dependent markup.)
We managed to fix this by changing the Akamai config so that the normal user agent from the website visitor is passed through to our servers in the request, instead of the Akamai one.
I suspect that this is also a bug in Sitecore (not returning the default markup for an unknown user-agent).