Turn off menu animations for one, as well as any other animations, if it's that slow. MS did away with the "personalized menu" in the Start menu in XP (That's what you're talking about, btw). If you have that many items in your start menu, you could turn on scrolling as that would cut the display of a few items at least. Last, make sure you don't install programs into the start menu directory, or store files there. My brother used to do that (don't ask me why) and the size of some of the files ate up a lot of time when Windows went to parse the directories.
/L.A
On second thought, I like Khayman's suggestion of categorizing/organizing your start menu, and the recently-used programs would actually be the replacement to the personalized menus of 98/ME