My Dad and I had this same problem about a year ago as well (approximately a week apart)... I'm not quite sure of what causes it, but it's total bullshit...
I didn't think this sort of thing happened anymore since the past few updates though... I haven't run across it at least.
I know Firefox doesn't store it's bookmarks into individual files like IE does, I'm guessing it uses a database file, but I can't seem to locate it... The only way to backup your bookmarks is by exporting them into an HTML file it seems. I'm guessing that database file gets reset when shit goes wrong with Firefox... Not exactly the smartest thing, especially since it doesn't seem to have a backup of any sort.
BoriquaSNK is right though,
del.icio.us is pretty useful, but you won't always feel the need to put
everything that you find in there, or even want to/feel like it for that matter...
My del.icio.us page for poops and chuckles. I've hardly updated the stupid thing in the past year because I always forget to.
Foxmarks looks interesting, I'm going to mess with it later.