Well first verify that wireless reconcile is working:
Send two emails from the user's mailbox
Delete - Outlook
Delete - Blackberry
Wait for both to deliver to both the user's mailbox & Blackberry.
Delete Outlook in Outlook, Delete Blackberry on Blackberry'
On Blackberry / messages / Bring up options and reconcile now.
Messages should delete on each location. You could also test the Purge Deleted Messages on the Blackberry.
If that all works it's working fine and likely a user workflow thing.
How old is the email that won't delete .. BES only tracks the last 100 by deafult. Is the email still in the mailbox?
If you have a large exchange environment you could move the mailbox as it cleans up quirkiness.