Danke für den Hinweis aufs Komprimieren und das Re-Indizieren.
Mittlerweile habe ich das in der Hilfe beschriebene (halb)automatische Komprimieren aktiviert und meinem Virenscanner den Zugriff auf das Profilverzeichnis verwehrt. Testweise habe ich auch bei meinen beiden Hauptordnern den Index neu erstelt - das ging fast zu schnell.
Ich bezweifele allerdings, dass Komprimieren und Re-Indizieren Einfluss die Laufzeiten beim Suchen bzw. den virtuellen Ordnern verkürzt hätten. Immerhin hatte ich die Nachrichten gerade erst aus Outlook importiert. Die Mailboxes müssten also eigentlich in gutem Zustand gewesen sein.
Wenn ich jetzt eine Suche nach ungelesenen Nachrichten über alles laufen lassen, dann geht das recht flott. Die Ergebnismenge ist allerdings (erwartungsgemäß) leer. Ich vermute deshalb, dass Thunderbird mit sehr großen Ergebnismengen bei der Suche Schwierigkeiten hat. Hätte ich allerdings auch