I am also having the same problem. Although the question may be simple, the answer is not so. Upon refreshing the desktop, all my icons rearange themselves as if I checked the "autoarange" itself. It is unchecked and it doesn't matter what you do to the settings, the icons always return to the left regardless if you restart or refresh the desktop. Unchecking the "align to grid" has no effect as well.
Currently I am using ICU; Icon Configuration Utility to rearrange the icons to where I want them. It works, but this isn't a solution.
I have also created another user, but Windows remember's the icon location for that. So the problem exists with my main user. I have a feeling it has to do with a corrupt registry file. I don't know what it is, but this is frustrating to say the least since there are others who have the same problem without finding an answer to this dillemma.
I've also tried the suggestion above by rebuilding the Icon Cache. No luck.
I also tried deleting the desktop.ini file and restarting the computer. No luck as well.
This problem that I have has nothing to do with viruses, trojans or worms. (oh my!)