Hey mate,
This sounds annoying. I have had similar experiences when booting into Windows 7 with the monitor off, in which case Windows 7 assumes a particular resolution because it cannot communicate with the Monitor, and at other times as a result of manually changing the resolution.
I suggest that you download an excellent program called Fences:
Fences - Windows Desktop Organization Software
With Fences you can permanently arrange your desktop items, and when your resolution changes, Fences adjusts accordingly. This program won't benefit the size of the icons as such, but it will certainly help you to put the icons where you want, and more importantly "keep them there!".
Best of luck
Regards,
Davo