I'd bet my next paycheck it's not the OS's fault but rather the app's fault.
The OS doesn't determine what gets put on the start menu... if the app wants an entry in the Start menu, it has to create one. And if the app was written for win9x and didn't follow the rules it's supposed to follow, it might not work properly under XP.
Don't blame the OS for the app's poor behavior.