Toolbar settings are saved in a file with the extension .xlb.

close excel
Use windows start button|Search
to find all those *.xlb files.
Make sure to look for hidden files and through hidden folders.

Delete them all (or rename them to *.xlbOLD).

Then reopen excel and modify a toolbar (just a few to test)

close excel and reopen it to test it out.

If it worked ok, delete all those *.xlbOLD files.

(I'm guessing you've upgraded through various versions and a couple of *.xlb
files are fighting it out!)

By deleting all the old ones, the "real" one can win.

When you're done making all your real changes, find that file and store a copy
of it somewhere safe--if you need to recreate the toolbar, you can just delete
the *.xlb file and copy the backup into its proper home.