Thanks Tomerg3,
I will feed this back to the Payment module developer. However, as per my diagnosis so far, this isn't strictly related to the payment module, or if it is, it must be a common error with all the three payment modules we use because the issue occurs irrespective of payment method.
I have done some more testing today though and discovered the following:
Enabling Litespeed makes the incedence rate increase dramatically, but I don't think it is the root cause. I turned it on today and flushed it and indeed we got a few issues. I didn't turn on smarty cache so that can't be the culprit. But even with Litespeed disabled we get the odd occurence.
Instead, I have had some weird behaviour whereby when I logged in to the front office using one of my accounts I use to test transactions, it brought up an abandoned cart that another customer had generated earlier in the day. I did see this happen once last year, but it also happened in the middle of the payment issues last week when an order came through from a completely different name to the payment.
I think the whole root cause is due to some issue with carts getting allocated or swapped between customers. If this does happen, then I assume the legitimate customer's order woud fail to complete, as suddenly there is no valid cart to convert. This would explain the payment issues, and the error log.
The smarty cache and Litespeed are red herrings because it happens with them disabled, even though it is worse with them on (no doubt as more data is held).
Any suggestions what may be causing this behaviour of carts getting reallocated to different customers, as I believe if we figure that, the whole payment problem will be sorted.
I am awaiting error logs from the server guys.