Ich habe gerade noch etwas merkwürdiges festgestellt:
Die besagten Mails liegen im Ordner "Bestellbestätigung". In diesem Ordner funkt. die Suche also nicht.
In einem anderen Ordner liegen auch automat. generierte Mails des gleichen Absender (diesmal sind dies Rücksendebestätigungen). Wenn ich in diesem Ordner befindliche Mails durchsuche, funkt. die einwandfrei.
Vielleicht hilft das weiter?