I've spent quite some time with one of the DBAs to try and determine the cause and came up with blanks. After a while I decided to check the deployment targets on the WebLogic server and found some oddities. Turns out someone half set up a cluster and didn't retarget everything to run on the cluster. The data source was targeted to the cluster, whereas the web service target was still just the managed server.
This is the error that I was seeing in the managed server logs:
The fix is simple, have both the data source and the web service targets the same! Once I've made that change the errors went away.