Mails erscheinen wieder

Dann kann es gut sein, dass entweder dein E-Mail Provider Serverprobleme aufweist oder der Account falsch konfiguriert wurde. Um letzteres auszuschließen, kannst du Versuch ihn neu zu konfigurieren, also ihn zu entfernen und wieder hinzuzufügen.

E-Mail-Account auf dem iPhone, iPad oder iPod touch hinzufügen - Apple Support (DE)

E-Mail-Account in Mail auf deinem Mac hinzufügen - Apple Support (DE)

Hey, ist das eine iCloud Mail?

Hast du vor dem Löschen oben einen Suchbegriff eingegeben?

Könnte sein, dass die Mails dann auf Grund der Suche wieder ins Ergebnis einfließen, weil auch die gelöschten Elemente durchsucht werden.