Leider ohne Erfolg.
Ich vermute, dass du auch schon direkt im Papierkorb gesucht hast. Standardmäßig werden die Papierkörbe nämlich nicht von der globalen Suchfunktion erfasst.
Ich hatte per mobile Web.de-App gesehen
Meinst du das, was man allgemein als "Webmail" eines Postfachanbieters bezeichnet?
Ich kann dir leider keine Lösung anbieten. Falls es sich um sehr wichtige Nachrichten handelt, kann ich dir eine Fernwartung vorschlagen, für den Fall, dass du etwas Entscheidendes übersehen hast.
Ich hatte kürzlich einen Fall im französischen Forum, wo ein Anwender die Unterordner seines Posteingangs nicht finden konnte. Die Lösung war sehr einfach: er musste nur seinen Ordner Posteingang "aufklappen", damit die Unterordner sichtbar wurden.