Can you find where your other browsers save their bookmarks, so that you can look at whether the bookmarks have been deleted - or if only the links to them (on the browser toolbar) went away?

Jon's comment suggests that Chrome has an autocomplete function that probably looks at bookmarks first when he starts typing. (Otherwise just typing mu... would more likely take him to a museum somewhere(?)) If that function works independent of whether the bookmarks toolbar is displayed, it implies that the actual bookmarks - and their URLs - are in a primary storage space elsewhere on the drive.

The expectation would be that turning off display of the bookmarks toolbar shouldn't delete the bookmarks that are on it, and that moving bookmarks on/off the toolbar shouldn't change the bookmarks actually present. The normal use of a toolbar of that kind is so that you can select the few items you expect to use frequently without displaying everything you have (although Chrome/Firefox/Safari designers may not be all that normal ;-).

Do the other browsers give you an alternate way of displaying bookmarks, such as a menu or other tool?

In IE, if you select File|Import and Export and Export Bookmarks, it will put a complete listing of all your bookmarks in one file (as an html "page."). If the other browsers have a similar export function, the exported file should tell you whether the bookmarks still exist, even if they no longer are displayed on the toolbar.

John