I'm currently using zenphoto on 59038images under 938albums and the script is terribly slow.
Does zenphoto really scans the albums directory every time the script is executed?
Is there a way to improve the script performace (without using eAccellerator,apc...)?

Zenphoto is file system based which is why you can conveniently upload via FTP.

Zenphoto also creates sized images on discovery which may take some time depending on your server power and the dimensions of the images used. Please read on the troubleshooting on our user guide about this. And also search the forum.

We have a static html cache plugin as well.