Update: an RU5 interim update and a RU6 update later, the issue should be solved according to Microsoft, but we should see the results in 120 days, now that sucks …
Symptom: Even when not-read message are disabled in Outlook, users automatically send “Your email was deleted without being read” to the sender. The messages are related to mails which are 120 days old.
Cause: In my case the user moves all his unread mails from his Inbox to different mapped PST files with Client side rules. The resulting not-read message is known bug in Exchange 2010 SP1 RU3. An interim update is available on demand (KB2471964), though we decided not to install it as according to Microsoft the issue shall be solved in RU4. Release of RU4, quoting a Microsoft employee, will be somewhere mid July 2011 (no promises).

Second Income Coach…
adwords help…