Way before this event I set up a git repo in my .mozilla directory and committed everything in the directory (except obvious cache files and such) in the repo. I didn't make a cronjob with this since I didn't thought of a proper way to make sure the browser wasn't started (the data might have been inconsistent at commit time), and, since most of the time I have the browser started, it seemed rather useless to try to automate for a very, very small window of time when the browser data would be in a consistent state. As a consequence, I did occasional manual commits in the git repo.
When the bookmarks issue appeared I realised that my last git commit was so old that it didn't made any sense to try to restore since I would have had lost bookmarks, passwords and plugins. So I made a checkpoint commit os the broken profile and resorted to all sorts of manual attempts at fixing the issue, but all my efforts of playing with the bookmarks.* files proved to be useless.
I concluded that icewesel/firefox 3.5.x was using some other mechanism and decided to dig into the issue at some latter time when time allowed me to analyse and fix it. Today was that day.
I began by creating a backup for the bookmarks via the Bookmarks Manager export function. After a hickup, it managed to save a proper bookmarks.html file. I tried to import that file, but the breakage remained.
Then I decided I should prepare for the worst, installed an addon which allowed me to save all stored passwords and created a new account (started firefox from the command line with 'firefox -ProfileManager') with the intention to transplant files from the old files into the new one. Short after that I realised that it would be smarter to commit the new profile, too, import the bookmarks from the backup file and replace the touched files back into the old profile.
After the import and closing the browser, git informed me that the modified files were:
At this point the modification of the binary .mfasl files looked very ugly to me, but I had a hunch that the only relevant file to my problem was the places.sqlite file and I went on to check the contents of the file with sqlitebrowser. After inspecting also the urlclassifier3.sqlite file (whose contents were unreadable), I decided to give it a try at simply placing the places.sqlite file in the old profile and see if the problem would be fixed that way. After all, I had the whole profile's state in git so any breakage could have been undone easily.
I started firefox using the old profile and the problem was fixed. Yay!
Now I have my bookmarks back and a suggestion for the mozilla people: please don't keep useless files like bookmarks.html in the profile once they become outdated, they are misleading.
P.S.: I still have to think of a way to make automated sane commits. Maybe I'll try to make an iceweasel/firefox addon. This could be a nice idea since I could learn something new, too.