I think I know where it's happening.
current_time() is called in the callback. That's called during PHP's shutdown process. Unfortunately the shutdown process sometimes/at random kills off the objects used in the process before the script is actually finished working.
It's a PHP bug, and I read it was described as a chicken and egg problem.
I have a feeling this wasn't the case in earlier versions of PHP4, and only started to become a problem with PHP5 and later PHP4.
It's the same reason that gzip headers were sometimes not recorded in the meta files and I had to add a hack in wp-cache-phase1.php to add them back in. I literally watched my debug log as the headers were added to the meta object, and then somehow disappeared by the time the plugin was due to write them out. Very weird.