Ich habe schon öfter erlebt, dass Suchen in völlig gleichen Ordnern in verschiedenen Profilen unterschiedliche Ergebnisse bringen. In der Regel leigt es daran, dass eine der beiden global-messages-db.sqlite Dateien fehlerhaft ist.
Deswegen würde ich zunächst mal die global-messages-db.sqlite Dateien bei beendetem TB löschen und TB neu starten.
Bei sehr vielen Konten, Ordnern und Nachrichten kann das Neu-Indizieren schon recht lange dauern.