Outlook: Gesetzte Farbkategorien werden beim Suchen im Postfach nicht angezeigt

Moin,

ich habe da mal was wo ich überhaupt nicht weiß wo ich ansetzen soll.

Outlook 2016 mit Exchange-Konto bei Domainfactory.

Wenn eine E-Mail mit einer Farbkategorie gekennzeichnet ist wird dies auch in der Emailliste des Postfaches angezeigt. Wenn ich aber im Postfach nach einem Begriff suche, in der diese E-Mail angezeigt wird, wird unter Kategorie in der Liste nichts angezeigt, als wäre diese nicht zugeordnet. Öffnet man die E-Mail selbst, ist die Farbkategorie jedoch zu sehen. Wenn man nach dem Suchen in der Liste einer E-Mail eine Farbkategorie zuordnen möchte, erschein teilweise eine Fehlermeldung „Nachricht nicht gefunden“ oder es passiert einfach nichts.
Anfangs hatte ich das Problem nur bei einem Rechner. Dann kamen immer mehr hinzu. Inzwischen habe ich 2 verschiedene Kunden, bei denen dieser Fehler auftritt.

Der Fehler tritt nur nach einer Suche auf. Sobald man ein Ordner direkt wählt, funktioniert alles 1A.

Wäre für Ideen dankbar.