You can the modify the DefaultIcon subkeys under these registry keys (Works for XP style Start Menu):
Just navigate to the key mentioned above, expand it, then click the DefaultIcon subkey and on the right side doubleclick the Default entry and replace %SystemRoot%\system32\shell32.dll,-23 with the path of your icon "C:\Any Folder\My Search.ico" (including quotes).
Hmmm..? It works for me without a problem. Tested it on two computers with different icons. What kind of icons are you using? The default size ot the icons in the right side of the start menu is 24x24, so best if the icon contains this size, should however also work with standard sizes, at least it should not make them unrecognizable.
You did put the path to your icon in quotes? (Important if there are spaces in it.)
Could one of you perhaps post a screenshot how it looks for you? I'm curious now what might cause this problem.
Ep, glad to see you come back and tidy up...did want to ask a one day favor, I want to enhance my resume , was hoping you could make me administrator for a day, if so, take me right off since I won't be here to do anything, and don't know the slightest about the board, but it would be nice putting "served administrator osnn", if can do, THANKS