I just trashed my history again. Same accident as last time. Was it my fault? Well, herein lies the problem. I pressed a specific key sequence which triggered the delete. However, it's very similar to a key sequence I'm using a dozen times a day. The only difference is the order of one down and one release key event.
But let me explain it a bit first. If you hold the Control key you can jump from one word to the next with the left and right cursor keys. If you also hold Shift you can quickly highlight a couple of words. I often highlight parts of the URL like this in the address bar. Then I press Delete and then I either add something new or press Return right away.
The problem is that I can trigger Firefox's Clear Private Data dialog with Control+Shift+Delete (i.e. if I don't release Control or Shift quickly enough). If I now press Return right away, which isn't all that unusual if you've done it a million times before, it will delete my history (among other things) instantaneously.
If Control+Shift+Delete is pressed the following dialog is spawned:
As you can see the "Clear Private Data Now" button is marked as default, which means that Return is the same as clicking on it.
Fortunately I just found a workaround for this issue. I suggest to follow my instructions if you're using Control+Shift regularly to highlight words. Trust me, losing your history randomly can be really annoying.
Step #1: Go to Tools -> Options -> Privacy.
Step #2: Press the highlighted "Settings..." button and untick all items.
After pressing OK there the Clear Private Data dialog will initially always look like this:
While this workaround doesn't actually address the real issue (the shortcut itself), it does at least prevent you from accidentially deleting your history.