This is an indicator that your site does not support mod_rewrite.
In the case where you create the cached images with mod_rewrite off, the images will be stored in the cache folder as "normal" path names. Zenphoto knows the cached image exists and uses this URL to access it. All goes well.
When you have mod_rewrite on and a file not in the cache the URL used will assume that the rewrite rules will break it down into the not-mod_write form. That seems not happening, so the image is not accessed nor placed in the cache folder.
So, I guess the bottom line is that you cannot use mod_rewrite.