For these older versions of Windows, most of the utilities on the general icon page are prepared for it. Use those, or, manually, in the registry, there's one key where they are stored. This is Items there shown on the startmenu are: At HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\explorer\FindExtensions there's a "Shellfind" and a "Static" key. Shellfind's the general search option, haven't found the way to change that yet... but underneath "Static" there's any other search function on your computer. Expand these till you find the "DefaultIcon" key and change the path in the string on the right.

Within 2k/XP (Me ?) the ShellFind/ShellSearch key (name differs) is moved to the "Static" key and changing the icons for general search (plus, search for computers and printers on the network) becomes possible.

In XP, with startmenu in classic mode, you'll find the regkeys/programs don't change everything anymore. That is, icons shown in submenus still work, but those for the main menu don't anymore. Even when changing it at the CLSID value for the item at HKEY_CLASSES_ROOT\CLSID\ (that is, changing the default value at the underlying "DefaultIcon" key) just won't work. Also, and we dug deep, there's no other registry setting(s) controlling it even. This means you'll have to manually edit the icons inside shell32.dll. There's more versions inside, here's the versions that get displayed:

Utilities don't take care of all yet, but at least they can all be changed. In steps:

• Go to your display properties (rightclick desktop, choose properties). At the desktop tab, hit the "Customize Desktop..." button. In this dialog, you can change My Computer, My Documents and
  My Network Places (plus the Recycle Bin), as shown on the desktop, but also in the startpanel upperright section.
• Go to the root of the drive you installed XP on, "Documents and Settings" folder. Inside is a folder named after the profile you're in, open and there's the My Recent Documents folder. Rightclick, choose properties, "Customize" tab, change from there.
  Also there's a folder called "xxx's documents", with the My Pictures and My Music folders inside.
  The last one has a "Customize" tab when going to its properties, first hasn't. You've got to edit the desktop.ini manually (check here). If you want to rename, btw, go to folder properties, uncheck the read-only attribute, hit apply and change directly (read-only will be set back when clicking OK).
• Other items in the right section have icon setting in the registry at HKEY_CLASSES_ROOT\CLSID. Clsid values there have an underlying "DefaultIcon" key, where you can set the path to your icon. Here's the values:
  {1A9BA3A0-143A-11CF-8350-444553540000} - Favorites
  {2559a1f0-21d7-11d4-bdaf-00c04f60b9f0} - Search
  {2559a1f1-21d7-11d4-bdaf-00c04f60b9f0} - Help and Support
  {2559a1f3-21d7-11d4-bdaf-00c04f60b9f0} - Run...
  {7007ACC7-3202-11D1-AAD2-00805FC1270E} - Network Connections
  {D20EA4E1-3957-11d2-A40B-0C5020524153} - Administrative Tools
  
  And some are at
  HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\CLSID:
  
  {21EC2020-3AEA-1069-A2DD-08002B30309D} - Control Panel
  {2227A280-3AEA-1069-A2DE-08002B30309D} - Printers and Faxes
  
• Left part of the panel has two sections. Upper part is for apps you pin to the panel, lower parts shows most used programs. Windows creates shortcuts in seperate folders, but these you can just rightclick, choose properties and change from there.
• When you've chosen to show your browser and email cliënt in the upperleft part, rightclicking doesn't work. We've found no references in the registry, main program icon gets displayed. Only way to change this is editing this icon in the application itself...
  ..then again, if you uncheck tthe option to display those, then rightclick the regular IE/OE shortcuts in your programs group, there's the option to "pin to startmenu". New icons get displayed in exactly the same spot, and since they're shortcuts, it's easy to change the icons :).

Notes:

• Whole right part of the panel uses 24x24 icons. That explains some bad looking icons, format is not common in pre-XP icons. A good icon editor can add this format to the icon file.