We have managed to resolve this after quite some digging.
It turns out that the issue stemed from a security issue with CPANEL, in a specific version that they hosting company had installed. Once the hosting company upgraded the version of CPANEL the issue went away.
Do you know what version of cpanel was causing the issue and what version you have now? I am having the exact same issue as you described also hosting using cpanel.