Pytanie czy to faktycznie konto Exchange. W nim powinny się kategorie trzymać obiektu i być synchronizowane z serwerem.
Co innego IMAP. Sprawdź czy przypadkiem twój AV nie analizuje treści maili i nie modyfikuje je sprawdzając pod kontem zagrożenia i jakoś przypadkowo nie wywala kategorii w kosmos.