If you extract the icons from the EXE files

I had considered this, but I think that would be putting a band-aid on the problem. The root of the problem is the fact that the icon cache doesn't have the necessary icon when it's needed.

I seem to remember that the desktop icons are stored in a file called "shelliconcache". Are the menu icons stored in this same file? Anyone know? TweakUI can force a rebuild of this file, but I don't know whether that would affect things or not.