I thought I should reply back that I got some of the items in the start menu fixed. I'm going to try to image and clean the start menu to see if it holds through a sysprep.
FWIW, I had this policy set by accident which took accessories and a bunch of normal items out of the start menu. Setting it to not configured fixed that portion of my problems.
User Configuration-->Policies-->Administrative Templates-->Start Menu and Taskbar-->Remove user's folders from the Start Menu
That setting was set to enable and as soon as I set it to disable or not configured our users start menu now had the 'Accessories', 'Maintenance', 'Startup', and other icons at the root of the start menu that were missing such as IE.