Well, well, well.. I've just reinstalled Windows 7 Ult. x64, and as you asked, Brink, immediately after the installation, the icons hide perfectly fine....
BUT!!!! I believe I know what's the darn problem causing the OS to not remembering the setting, it's called a Power4Gear Hybrid (from ASUS), which interferes with the advanced power plan settings in Control Panel. I noticed this when I started installing the drivers, and immediately after switching to 'High Performance Mode' the icons came back!!
...and I have to untick show desktop icons twice for them to hide, but they came back after a reboot anyway.
I almost give up with the icons as the Power4Gear thing is handy to me as it controls the CPU clock and stuff so I don't have to DIM (do it myself<--DIY lol).
I just figured this out accidentally on my other Asus laptop. So, a try for looking at the advanced power plan settings in Control Panel might be worthwhile.
For l0w33ji, this might solve the problem caused when connecting/disconnecting the power cable, as Power4Gear automatically disable/enable certain features to conserve energy; including battery saving desktop, hide gadget and certainly desktop icons...
I agree with Zardoc, "Laptops, full of useless toys", implicitly.