I am seeing similar issue to what Sean is seeing. The difference is I am using EV12 SP1 brand new environment. All Search Policy and Search Provisioning Groups have been setup sorrectly. I can delete archived mails via deleting EV shortcuts etc.
Mailbox synced and everything but still no Delete option, I can see the Delete option for the deleting a folder though just not for the archived email(s).
Anyone seeing this too or am I missing something very obvious.