This is a symptom that your shutdown is not working "gracefully" or in my own terms "correctly". Either your computer is doing a hard shut off or windows is killing RR before it has a chance to save the resume info -- this could happen if you have used some of those "optimization" registry settings for xp shutdown specially the ones that reduce the amount of time that an application has to close on shutdown before windows kills it. If you have used anything like that, please remove those settings and try again.
If you can do this, I advise you to simply WATCH the shutdown process to see if anything seems weird, but RR itself should be doing the same when you shutdown windows as it does when you exit it.
Lastly, I don't believe this matters, but be sure that you have "RR is aware of hibernation/shutdown procedures" setting CHECKED in RRConfig.
I use the exact same procedure (Shutdown controller) and have never had any issues with restarting -- I do in fact power off instead of hibernate.