Possible this is a result of the malware, I just do not know.
You should be able to arrange folder as you wish, for instance:
My Documents > View > Arrange Icons by...
The problem is not so much that the folders have been rearranged, but that several major folders aren't there anymore. Everything works OK, so I guess the files are there somewhere, but I can't find them using File Search. I'll contact one of the Windows XP forums and let you know what I find out.

For your issues with files/folders in Firefox, I suggest you uninstall the program and download it again. It will install all files and folders it requires:
That is what I did. The orphan folder was left behind after Uninstall. I'm worried that it may include malicious files that will be inserted into the new version of Firefox, so I'm reluctant to do the Installation without finding out what they are.