I have discussed this with our server admins and it seems this issue is related to eAccelerator.
That might also explain, that the error has been also noticed on this site, as this server uses eAccelerator as well.
On other servers, we use PHP APC, which seems to be more relieable. I think there might be some bug in eAccelerator. Anyway, I am positive now this is not directly related to JoomSEF.
So, there are 2 options I see:
1. switch off eAccelerator or use different accelerator solution
2. restart the server when the error occurs (I believe it might be automatized using a system script)