Looks like an I/O problem.
As in, on startup Caja is reading a lot of files from disk. This would explain why it's only the first time. (after that the files are cached in RAM so it's faster)
I had a similar problem with mate-settings-daemon a while back.
Maybe you can use the same method for diagnostics?