Maybe it could be a permissions issue? I set up Quick Launch and I haven't had your problem. However, I run as Admin. Maybe it doesn't remember if you run as limited user? Or maybe you need to set it up and add icons running as Admin and then drop back to limited user and then it will remember?
Does it shrink to the same two icons each time? The bottom most ones in the list? Or is it random which it shows after rebooting?
Mine recently added ON ITS OWN "Switch Between Windows" and "Show Desktop". I wonder if those are supposed to be there by default but were not when I set up Quick Launch on Win 8? I really like "Switch Between Windows".