You say all your programs are listed via:

C:\Documents and Settings\All Users\Start Menu\Programs

Yes? Can you Drag & Drop these on the Start Menu > All Programs?

2 more things to try:

1. Switch to Classic Start Menu by right clicking start Properties
Just to see if that changes anything.

2. Try Safe Mode
Just to see if that changes anything.

I'm not in as much of a hurry now to fix the XP Start menu and XP Explorer menus...I believe there are maybe a couple of tweaks here or there that someone somewhere knows about, even written a macro to fix it. Hello Microsoft?
Meanwhile I've found a couple of free killer utilities that more than replace the XP Start menu and XP Explorer, adding way more functions besides! You may not want to go back there yourself after you try them ...

Start menu replacement: XP SysPad V6.1 at http://www.xtort.net/xtort/xpsyspad.php
Windows Explorer replacement: xplorer² ''lite'' at http://zabkat.com/
Windows Explorer enhancement: FastFolder by BB ver 3.3.0 at http://www.dogkennels.net/fastfolder/

I'll bet these guys ^^^ know how to fix it!
--------
droidbot7000

Before criticizing someone, walk a mile in his shoes. Then you'll be a mile away and he'll be barefooted.