Thanks for the response, that gave me some additional items to verify. I neglected to mention that we had previously changed our environment such that the ENS traffic bypassed our exchange load balancer and went directly to one of our Exchange servers, but this made no change to our issue. This traffic is also passing through a load balanced reverse proxy, so today I reconfigured those so that ENS traffic always uses the same reverse proxy and also bypasses the Exchange load balancer (and goes directly to a specific Exchange server) and we still have the same issue.
Airwatch thought that this might be an EWS authentication issue because they only support 'basic' authentication and 'basic' authentication was not enabled for our EWS virtual directory, but after enabling this, it also made no difference. I know you said your cloud based, but did you have to make any changes to your EWS authentication settings? (I don't know how this work cloud). If the authentication settings were wrong, I'm not sure how this would work at all, let alone randomly, but it's the only other lead I have.
Thanks