If it happens every "N number of times", that means one of the proceses has some stale data (something wasn't cleaned out completely on a previous invocation). Make sure you're not falling into any of the traps of Apache::Registry by reading the excellent mod_perl handbook at the site.
Thanks merlyn - I've spent the last few days re-writing code to cater for the various Apache::Registry gotcha's and managed to convince myself that this was another one.
But 5 minutes ago I realised it was just me being stupid - I had an empty hash, the code normally works because of the persistence that is provided but it wasn't explicity initialised in the section of the code dealing with these requests.
Sincere apologies
Jonathan /me wanders off feeling more stupid than usual