Falls das Problem immer noch besteht...
Ich hatte selber das Problem und habe es wie folgt gelöst:
im Profil-Ordner die Datei global-message-db.sqlite löschen
dann alle *.msf Dateien löschen
dann Thunderbird wieder starten und alle Ordner neu indixieren (ich bin einfach mit den Pfeiltasten durch alle Ordner gegangen).
Die Suche funktioniert seitdem wieder richtig. :zustimm: