I've used firefox for years, and never had your lost bookmarks experience--but one suggestion, FWIW--I use the Foxmarks bookmark synchronizer add-in to keep my bookmarks in sync across multiple machines. Apart from just being a slick add-in for its intended purpose, it strikes me that it may take care of issues like this to some extent, insofar as it essentially uploads a backup of your bookmarks to a server somewhere, which is then downloaded to your PC(s).