To change the web browser icon in the Windows XP Start menu:

1. Click on "Start" and go to "Run..."
2. In the run dialog type "regedit"
3. Go to "HKEY_LOCAL_MACHINE\SOFTWARE\Clients\StartMenuInternet\" by expanding the appropriate branches of the tree.
4. Select the web browser that you are currently using.
5. You can now modify the (default) key and rename the shortcut to whatever you want.
6. To change the icon expand the selected client and click on "DefaultIcon".
7. Change the (default) key to point to the icon file of your choice by double-clicking it. If you are going to use a file with multiple icons inside you should specify with a comma after the target the index number. (eg. C:\icons.exe, 2)
8. Reboot your computer for the changes to take effect.

Special thanks to Dan Ciuperca for helping me to change the email icon in the Start menu.