Alright.
I think I remember. It's worth a try.
1. Create a folder and name it whatever you like.
2. Put all your shortcuts into the folder. Includes desktop.scf
3. Right click on the taskbar, toolbar, then New Toolbar.
4. Select your folder
5. It should appear on the right like Jacee's.
Try to reboot now. If after the reboot the toolbar is still there, your problem is fixed. otherwise, I have no idea.