Not sure this is worthy of an answer, but too much to put as a comment. The only time I have seen anything remotely similar was with this and I was able to prove to support that a job had run and created duplicates.
The info I got back from Tier 3 at the time:
As we discussed, during the execution, an internal server error on the asynchronous process for the batch, resulted in cloned message in the asynchronous queue to not be removed resulting in duplicate messages getting worked. As a result of unlucky timing when an exception is thrown, this may result in cloned messages not being deleted and actually executed in parallel to actual messages
A Bug has been logged to fix this issue from Salesforce end.
It is scheduled in patch release next week.
'Last week' was just over 2 years ago. I can share my case # if you wish. The case status is currently: Closed - Bug Fix Submitted
Worth noting our customer stopped using our app ~6 months after but I never saw a re-occurrence in that time. It would also have been an EUn pod.
Good luck.
