Unable to soft delete messages after installing Exchange 2010 SP2 RU6 or SP3

Finally, Microsoft has confirmed that what we wrote and many users wrote on the forums.

Namely, Microsoft admits that after installing Rollup 6 for Exchange 2010 SP2 or after the installation of Service Pack 3 for Microsoft Exchange 2010, there are problems with the removing some of e-mails using soft delete:

1. Unable to soft delete messages that contain voice mail attachments.
2. Unable to soft delete messages sent from FAX server, printer or scanner which have attachments (such as .PDF).
3. issue occurs when you use Microsoft Outlook in Online mode or OWA

This issue does not happen with messages sent by a user instead of an application, or plain messages without attachments.

As workaround Microsoft recommends:

1. Hard delete the message instead of soft deleting – to hard delete email using Microsoft Outlook, select the message and then press SHIFT+DELETE to delete it
   
2. Use cached mode for Outlook – when using the cached mode of Outlook, the message can be soft deleted

All article is available here:

Unable to soft delete some messages after installing Exchange 2010 SP2 RU6 or SP3