I tried it with a fresh install:
1 - created one album with mtime decending in options->image
2 - uploaded 100 images
3 - edited the default theme with printLatestImagesByMtime(27) on the index
4 - everything looked oké, all 27 images have the same order, both in printLatestImagesByMtime as the album
5 - uploaded 9 new images
6 - the order between the first 9 images of printLatestImagesByMtime was not the same as the album
7 - uploaded 9 new images
8 - first 9 images have the same order, but images 10-18 have different order, but it's also different then the order i had in (6).
9 - uploaded 9 new images
10 - all 27 have the same order
11 - uploaded 9 new images
12 - 2 of the newly uploaded images have "switched places".
It looks so random, that i'm afraid i'm doing something incredibly stupid
I also posted it in the bugtracker.