... an denen ich schon längst die Markierung wieder entfernt habe. Ich finde keine Gemeinsamkeit an den Mails.
Jemand mit dem gleichen Problem?

Ja, geht mir ebenso. Das ist für mich ein echt lästiger Fehler, da ich die Markierungen intensiv nutze.
Einziger Workaround bisher: Die betroffenen Mails per Drag & Drop in einen anderen Ordner ziehen, dann erscheinen sie nicht mehr unter „Markiert“. Danach kann man sie ggf. wieder zurück in den Ursprungsordner legen.

Kennt jemand eine richtige Lösung?

Ich hatte auf dem letzten Mac auch einige Markierungsleichen, allerdings äusserte es sich so, dass an dem "Markiert" Ordner zwar die Anzahl der angeblich markierten Mails stand, diese Mails im Ordner selbst aber gar nicht mehr vorhanden und damit auch nicht aufzufinden waren.

Seit 2 Wochen habe ich einen neuen Mac und habe alles mit dem Migrationsassistenten rübergeholt, die angeblich markierten Mails sind jetzt aber weg.

Die Ursache liegt damit aber weiter im Dunkeln.

Aktuell verschwinden wieder alle Mails aus dem Ordner, an denen ich die Markierung lösche. Also wie es sein soll. Einen zeitlichen Zusammenhang mit einem Update gab es nicht. Auch sonst hab ich nichts (bewusst) unternommen.
Wie ist bei euch der Stand und mit welcher Systemversion?