After I upgraded to Nextgen Gallery 2.0 (used in WP3.6) I have created a new gallery and stored 560 images in it.
Pagination or not, the gallery does not show more than 500 images in the gallery.
I've rolled back to Version 1.9.13 and instantly all pictures are visible.
After the rollback I noticed a significant performance boost in loading the thumb nails, looks like 2.0 is much slower in loading pages with much pictures than version 1.9.13.
Some can test and check, and hopefull solve the issue, as I'm impressed about the thumbnail effects in 2.0