In letzter Zeit hatte ich ein paar Fälle, wo die User in regelmäßigen Abständen folgende Nachrichten erhalten:

Ihre Nachricht
An: Schoch, Malte
Betreff: ungelesen gelöscht
Gesendet: Donnerstag, 08. September 2011 15:06:15 (UTC+01:00) Amsterdam, Berlin, Bern, Rom, Stockholm, Wien

wurde am Montag, 16. Januar 2012 19:57:43 (UTC+01:00) Amsterdam, Berlin, Bern, Rom, Stockholm, Wien ungelesen gelöscht

Dieses Problem sollte laut Microsoft mit dem Rollup 6 für SP1 behoben sein:
http://support.microsoft.com/kb/2544246

Bitte beachten Sie den letzten Absatz in dem Artikel:

Hinweis Die NRNs sind nicht vollständig geleert, bis 120 Tage vergangen sind, sobald der Hotfix installiert ist. 

Das bedeutet, dass es nach der Installation immer noch einige Nachrichten verschickt werden können.
Um dies zu verhindern oder eine schnelle Lösung bereitszustellen, ohne das Rollup zu installieren, können Sie eine Transportregel erstellen, welche diese Nachrichten verhindert: