How I discovered the problem
As I learn a lot of mathematics, most of my notes refer to earlier notes. For example, an «ultrafilter» is a special kind of «filter». Thus, I first create a note «filter». I then create notes to learn the principal properties of filters. Then I create a note «ultrafilter», and some notes to learn their principal properties. Anki showed me a question about some property of ultrafilter, and I realized that I had forgotten what a filter is. I first thought that, it's not a problem, anki will surely show me the definition of filter soon. But this occured many time, and I find it strange. I thus went into the browser and check when the «filter» card is due. I realized that I've got no «filter» card in my browser. And in fact, that a lot of cards related to filters were missing.
I thus went into ~/.local/share/anki2.1/USERNAME/deleted.txt, the file in which a copy of every deleted notes is kept. I went searching for this missing note. I found the note. I did take a loot at the note deleted before and after this one, and realized that a lot of them were also missing from my collection. Thanks to an old version of the add-no explain deletion, I also learned that all of those cards were missing for the same reason. Those note had no more cards. That means that I used «Check Cards...», and it discovered that every single card of the note were deleted, thus the note had to be deleted too.
Now I was sure there was a problem. It remains to repair this problem.
First thing first, I wanted to make sure that this problem won't ever occur again. I created this add-on which will warn me when «Check cards...» find a note which has no more card. That is really what I want,, because having a note without card is certainly the sign that something wrong occured. And when something wrong occurs, I believe that «deleting it» is far from being the optimal solution. Actually, I was quite mad at Anki's author that this was what he considered to be the way this problem should be dealt with.
Then, I had to figure out exactly which cards were deleted by accident. I assumed that every notes deleted by accident were deleted simultaneously, and thus appear one after the other in the file. I strongly hope that it is the case, otherwise, there are deleted notes that I never found. But since there are 127 844 deleted notes, I can't check them all manually.
Using dichotomy, I found which was the first and last notes which were mistakenly deleted; which was missing from my collection. I then made a copy of all of those notes into a new file ToRecover.txt. I checked a few notes randomly selected from ToRecover.txt, none of them were in my collection, and all of them should be in my collection. I checked also a few notes which were in deleted.txt and not in ToRecover.txt, and all of them were either notes which I did want to delete, or note which are in the collection. I then realized that I had more than five thousand notes which were missing. Honestly, it flabergastes me, because I would have believed that I would have noticed that 10% of my collection was missing. In fact, I believe that it took me more than a year without seeing a note before I realize that I have not seen it for quite a while.
Then I created the add-on undelete, which, given the file ToRecover.txt, add back the notes in the collection. As explained in the add-on's readme, this add-on is far from being perfect. I won't repeat every single problem it has, and will only consider the problem I have dealt with.
deleted.txt contains the creation date of each note. I thus was able to enter this information in each note. This means that anki can indeed show me each new card in the order in which they were initially created. As I explained above, the order in which the definition are learned is really important for me, hence it is a really good news.
The file deleted.txt does not contains the name of the deck of the note (which makes sens, since cards of a note may belongs to distinct deck). It means that I have to move every card in their own deck by hand. I started doing that and I realized that, actually, it's quite easy to do hard.
Decks are really important for me. I have one deck by programming language, for example, one deck for algebra, one deck for analysis, one deck for economy, one for biology. This allow me to see a single new biology card by day, a single new algebra card by day, and so on... This also means that finding the deck of note is not exactly complicated. For a lot of note, it's not exactly hard to know whether it's related to bio, to economy, and so on... But still, I didn't want to move 5000 notes by hand.
However, I was able to use the creation time of cards to help me find out the correct deck for each card. When I want to move a recovered note, I look at which note was created just after/before this recovered note. Usually, it allows me to find very quickly the correct deck. Since furthermore, my notes show the page number, if I see that the sequence of creation time is consistent with the sequence of page numbers, I can be sure that I have found the right deck.
Actually, I wrote a code (which I don't share as an add-on, because I don't think anyone will really be able to use it), which did exactly this. It took a look at every recovered notes, and moved them to a deck if the note before and after this note both belong to the same deck. This did moves more than 3000 cards. (I don't know how many note it did move exactly, I didn't count that.)
One of the worst problem of the «undelete» add-on is that deleted.txt separate fields using the 'tab' character. So as soon as a field contains tab, it is considered to be two distinct fields by my add-on, and I've got no way to avoid this. If the 5th field contains a tab, then the 6th field of the created note will contains the end of the 5th field of the original note. The 7th field will contains the 6th field, and so on... This means that, until I've actually seen those 5000 new cards, I'll now I'll sometime have to correct this error. This risk to be extremly long. Luckily, it seems that it did not occur very often. While I was looking at the new card to check whether undeleting seemed to work, I didn't see any instance of this problem.
The biggest problem however is that the note type was also missing. I still had the note type's name, but some note type have changed a lot between the day of the deletion and today. Let us imagine that, in some note type N, I did add a new first field. It means that every single field content in every single note whose type is N should be moved to the next field. It's quite a lot of work to do. The good news is that, since all notes were deleted at the same time, all notes whose type is N used the same version of N. So I can change a lot of notes simultaneously.
There is a strange problem with anki. The order in which new cards are seen is EXTREMLY wrong, and does not correspond at all to what is indicated in the manual. The change I did above totally breaks the order of new card. Happilly, an add-on corrects this. Thus I used this add-on.
Some decks had lost a lot of notes, while some other lost none. I can not explain why it is the case, which probably mean I have not entirely understood how the problem occured in the first place. And I some time knows very well the lost notes.
So, I changed the deck's option of those decks, so that I'll see them four time quicker than what I normally do. Hopefully, in some time, I'll change them back to the standard option I use. This will allow me to see quickly those recovered cards, which anki consider as new, but which are not really new.
 actually, it's unique identifier