Im not sure about this, I guess its not random but who knows, I have seen randomness before on the ps3.
Here is one place I have seen it. My CFW Toolbox application installs about 20 applications in one go, it just copies all the data into the game folder with xai_plugin and then rebuilds the database. Well every time I do that, the apps end up in a different order on the XMB, seems to be random. You would think it would copy in the same order every time and then the database rebuild would find them in the same order every time, but no.
Have you tried this, if you just throw like 20 random small packages on there, is it always the same order? If it is always the same, you need to do that, and then analyze the order and the packages to find the difference. Try things then like repacking 1 package, and renaming 1 package, to see if that changes the order, its probably simple enough if its not random.