Web Service failures when virtual machine has time skew

Issue

We have a RHEL virtual machine running on VMWare, and an application which makes Web Service calls to another server. After around two weeks the web service calls start failing, and when they do all requests fail. Restarting the application or even the whole virtual machine does not help, but building an identical virtual machine does.