I realize this is an old request, but I have been looking for an answer to the same questions and was never really successful in finding a solution. I finally found my problem and thought I would share it here just in case it helps someone else.
I was able to delete the custom toolbars by importing all components of the old database (e.g. tables, forms, queries, etc) into a blank Access 2010 database. But I still kept getting an annoying "Microsoft Access could not find the toolbar "MyCustomToolbar".
So it obviously deleted it, but something was still looking for it!
I searched all of the VB code for "Toolbar", "Menu", anything I could think of and could not find anything in the code that referenced custom toolbars. What I DID find, was that certain forms were attempting to invoke those toolbars in their Properties.
I had a handful of forms that were doing this and this is how you find them.
SOLUTION:
Open up a form's Property Sheet and select the "Other" tab. In that tab were variables "Toolbar" and "Menu Bar", each of which was filled in with my custom Toolbar from the original database.
Clear out any of the entries related to your custom toolbar and the messages disappear!
I hope this tidbit helps other users from spending the hours that I did trying to track down this annoyance.