IGN,
Я разобрался - он "видит" даже те непрочитанные сообщения, которые ты удаляешь браузером, к примеру, - зашел во входящие, не читая их в корзину поудалял - все, ПМ покажет их!
Пришлось вручную прошерстить все папки всех ящиков (в каждую зайти, нажать "обновить", поудалять найденное... мрак!), чтобы избавиться от этого уведомления ;)