I'm using Win7, x64 with Classic Startmenu, most recent version:
When restarting the PC or clicking on "shutdown" via Classic Startmenu, desktop icon positions that have changed in the current Windows sessions, are lost and forgotten upon next startup.
This does not occur if I click Shift+Win-key to bring up the original Win7 start menu and shutdown the PC from there: all desktop icon positions are remembered.
So this bug seems to be caused by Classic Startmenu. Maybe you are just terminating Explorer rather than asking politely to quit?