Hallo MT,
Kannst Du bestätigen, dass Du die Suche nach gekennzeichneten E-Mails (mit Flag) korrekt durchführst, wie in diesem Artikel beschrieben:
Überprüfen gekennzeichneter E-Mail-Nachrichten
Wenn der oben genannte Schritt korrekt ausgeführt wurde, kannst Du versuchen, in Outlook 2016 vom Exchange-Suchindex zum Windows-Suchindex zu wechseln. Der Windows-Suchindex bietet einige Funktionen, wie Kategorie und Flag, die nur bei Verwendung des Windows-Index verfügbar sind. Der Wechsel erfolgt durch eine Registrierungsänderung, wie in diesem Link deutlich gemacht wird:
Outlook 2016 - Search results not showing categories or flags
Gruß,
Ivan Dragov