Isso ainda não foi confirmado pela Microsoft, mas depois de ler centenas de tópicos sobre esse problema, parece que esse recurso não é um bug. Parece que a implementação de servidores da Microsofts Activesync está agrupando pequenos "eventos", como excluir e-mails, sinalizar e marcar como lidos. Esses eventos estão atrasados (no meu caso, 10 minutos) antes de serem enviados para o celular. Se um novo e-mail chegar, os "eventos" secundários serão enviados com a "nova notificação de e-mail" que chega em tempo real de qualquer maneira.
Eu testei esse problema no Exchange 2010 e no 2007 SP1 e parece que ele pode ser reproduzido nos dois ambientes com facilidade.
Por favor, corrija-me se você sabe que a minha teoria está incorreta. Para me repetir, eu não tive isso confirmado pela Microsoft.