I had to do a complete reinstall of Windows XP including Service Pack
2 and now, every time I reboot anything that was in the start menu?s
?recently used programs? listing disappears, anything that was pinned
to the top of the start menu disappears and the default programs which
were there on the original install re-appear such as ?{Tour Windows
xp?, Windows Movie Maker and ?Files and Settings Transfer Wizard?.
Also on reboot the start menu automatically opens everytime.

That's so possibly because you are using a cracked copy of Windows.
The thing is that everytime it runs it thinks that it is run for the
first time, so no activation needed any more. Think you need reinstall
your Windows from another CD, the licensed one.

Such it is possible and on absolutely license version Windows XP (as at me)
So, that your assumption - erroneous.

At users with an old profile with list MRP everything is all right,
and for new users - MRP cleared each time after an exit from system is
. Removal DEFAULT USER Profile does not influence result.