I'm running Windows 7 Ultimate x64. Have been having the same issue for a while.
I have custom toolbars which point to shortcuts, each in a separate folder stashed in ProgramData, for Taskmanager, Lock, Restart, Shutdown.... (all of them saving me a couple of extra clicks for those functions)

Losing my custom toolbars at random, after reboots or shutdowns, is a pain in the rear. I've tried all of the different registry tricks designed to make them stay put...none of them have worked.
The only "solution" I've personally found is to backup my custom toolbars and restore them, using a couple of .bat files I've made. Then, whenever I log into my computer and find that my toolbars have disappeared, I just double-click my "Restore-Taskbar_Toolbars.bat"
and they're instantly back.
I found the original backup/restore tutorial **Here**at Windows SevenForums, written by Shawn Brink.
My customized .bat files, however, unlike the ones you can download from SevenForums, create the " Taskbar-Toolbars-Backup" directory in your system's ProgramData folder instead of on your desktop....Thataway, you can just keep the .bat files in that same folder, backup and restore from it too, without needing to drag the folder to your desktop each time.
* Since ProgramData is a normally hidden folder, you'll need to un-hide it via the 'Folder Options' menu in your Control Panel. Under the 'View' tab, put a tick in the "Show hidden files, folders, and drives" option.
- Download my custom .bat files HERE.****Save them to your desktop.
- Unlock the taskbar. Get your custom toolbars set up the way you want them to be. Lock the taskbar.
- Double-click the Backup-Taskbar_Toolbars.bat
- Open your ProgramData folder and look for the new Taskbar-Toolbars-Backup directory. Open it and ensure that the Taskbar-Toolbars-Backup.reg file is inside.
- Move both the Backup-Taskbar_Toolbars.bat and the Restore-Taskbar_Toolbars.bat files into that same folder. From now on you can launch either from there.
- Next time your toolbars disappear, just open that directory and double-click the Restore-Taskbar_Toolbars.bat. And each time you re-arange or change or add to your toolbars, delete the previous Taskbar-Toolbars-Backup.reg and run the Backup-Taskbar_Toolbars.bat, which will create a new backup registry file.
* No, it's not a "solution" to the disappearing toolbars bug, but it saves a bit of time & effort, especially if you have 3 or more toolbars and lots of shortcuts in them.
* Thanks to Shawn Brink @Windows SevenForums for the tutorial.