I'm gonna continue to guess that there are at least two versions of your *.xlb
files. One of them is in the XLStart folder.
The first one (in its real location) gets loaded with the toolbars where they
should be.
But excel sees the *.xlb in your xlstart folder and loads that. And that
supersedes the "real" one.
And each time you close excel, the "real" one gets changed -- but not the one in
XLStart.
My "real" one is in:
C:\Documents and Settings\(username)\Application Data\Microsoft\Excel
And my XLStart folder is in the same location (but it doesn't have *.xlb's in
them anymore!)
I'd use windows|start button|search to find all those *.xlb files.
(Remember to search through hidden folders for hidden files, too.)