Has this issue ever been satisfactorily resolved?  I too have this issue with cute empbedded in a ASP.NET.  There appears to be a threshhold for nomber of images for us as well, and creating new folders is not an acceptable solution.  All image gallery dialogs would probably perform better is views were paginated with sortable columns (that default to most recently uploaded/changed), alphabetic filtering, and a search box.

Has cute tested this with a scale of thousands of images?