To correct this problem with IE 4.x, use Regedt32 to navigate to:

HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\MenuOrder\Start Menu\Menu
and Delete the Order value name in the right hand pane.

You must restart your computer for the change to take effect.

NOTE: You may have to repeat this process every time the menu is changed.

NOTE: I suggest that you remove the Windows Desktop Update, if installed, using Q165695 - How to Add or Remove Windows Desktop Update. If you wish to keep the Windows Desktop Update, upgrade to IE 5.x.

To correct this problem with IE 5.x, right click on any object in the menu and press Sort by Name.