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.

That's correct. I attached a .reg file that increases ths size of the icon cache file to 2048 from the default (1024). You can edit it (like all .reg it is a simple txt file) and change it to whatever value you prefer.
If you want, you can edit manually windows' registry. Here's what's in the .reg file I attached:

REGEDIT4



[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\explorer]

"Max Cached Icons"="2048"

This should solve your problem