The executable not recognised thing is a red-herring I'm sure.
The problem seems to be some kind of process-level lock on locale resources.
A single instance of valgrind over all our processes runs fine. The issue is not the application, it is the parallelisation that I have introduced by using Python's multiprocess module in order to run batches of valgrind together. One valgrind instance takes about a week to run over all our processes which is why I started to explore the multiprocess route. For the moment, I'll scale back and be patient until I understand the locale issue.
Thank for your help.