The things I've seen re-arrange icons:

1) Back in the Windows 95/98 days, a Windows crash (whole machine) would often reset their position and they'd end up in alphabetical order

2) Windows XP auto-arrange (as mentioned)

3) Remote desktop to the machine in full screen from a machine with a different resolution (lower)

Are they all moving, or just one or two? In to alphabetically (or some sorted) order? You say randomly - how random?

Have you seen it yourself? I'd almost say operator error perhaps?

My XP machine has stacks of stuff on the desktop. I have align to grid but not auto-arrange on. It never moves the icons. The only time I do have trouble is with full screen remote desktop which also changes things like the refresh rate which I have to change back when I use the machine normally.