interesting observation re: All My Files view possibly having something to do with it
in my case, I only have my 1 userid. and the problem has happened ever since 10.7.0 for me. However I gave your idea a try anyhow. my All My Files view was set to "arrange by Date Last Opened (meanwhile Home folder set to Arrange by None)
I changed view settings for All My Files to Arrange by None, logged out then logged back in again
then I tried my usual trigger for the problem, i.e. Mail, save-as an attachment to some folder.
but the problem still occurs for me. if I get a chance I'll try some other setting combinations, in case there is some kind of effect with the All My Files view...
an aside: I notice that every time my home folder gets messed up, it's the same identical icons that get moved, and they all get moved to exactly the same place. anybody else notice this too?