When you say you reinstalled XP - what sort of install was this (eg, was it a repair reinstall, or did you just do a new install 'on top' of existing installation, or something else)?
Because, unless it was a repair reinstall, most of the programs will need reinstalling too (as all registry entries and system files associated with them will have been removed).
If it was a repair reinstall, all the programs should still be installed properly (and in fact you'll still be in same position - apart from Windows apps, which the repair will probably have recreated shortcuts for you - which might account for 'got some of them back, but not all). Depending how you 'managed to break all the links in the "All Programs" menu' - did you delete stuff from All Users profile? - you may need to manually create shortcuts from the .exe files & place them in All Users Start Menu\Programs.
