When a delete policy is applied to a folder and Outlook is in "Cached Mode", the mails are still visible to the user.
Outlook has cached the deleted message.
An Exchange administrator can confirm this by opening the users mailbox as a delegate mailbox in Outlook and viewing the folder. If the mails do not appear then the delete policy has sucessfully deleted them, but the on the users Outlook the mails are cached.
Turn off Cached Mode.