Messages are not being stripped from random folders (eg: subfolder, inbox and sent items) even though stripping policy has applied as default policy at server level.
Move the problem mailbox to another mailbox store and move it back to its original location.
If you have large amount of mailboxes having this issue, you can use the Microsoft ESEUTIL to repair the database.
Refer to Microsoft KB Article ID 816576 - "Exchange Server Database Utility Guide"
It appears that moving the mailbox cures the issue. It appears there is corruption in Exchange that the move forces Exchange to clear up.