On 3.1 and below:
- select all
- unsnapshot
- close window
- open window again
- clean up
- select all
- snapshot
On 3.5 and above:
- cleanup by name
- select all
- snapshot
You probably forgot to snapshot.
And this only works with real icons, not with "show all files" dummy icons. Dummy icons are ordered by name anyway.
