Edit 30-5-2013: Exchange 2010 SP3 RU1 has been released to address this issue. Details and download are here.
Quick heads up on an issue from Exchange 2010 SP2 RU6 and that is also in Exchange 2010 SP3. After installing either of these updates, users may report that they are unable to delete certain items when in online mode.
This issue does not surface when running Outlook in cached mode.
Workaround 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.
Workaround 2: Use cached mode for Outlook.
When using the cached mode of Outlook, the message can be soft deleted.
Please see KB 2822208 for details and updates on this issue. In addition the community is active in the TechNet forums which can also be followed to stay up to date.